动态规划

数位DP

基础知识

• OI-Wiki

• 3007. 价值和小于等于 K 的最大数字

  • 只想到了普通的记忆化搜索

位运算

2088. 统计农场中肥沃金字塔的数目

• 二维转化为一维DP的时候，一定要注意递归过程中会不会覆盖此次递归需要的旧值
• 这题第一次提交错误，就是因为当前更新时覆盖了旧值，但是之后的计算需要被覆盖的旧值；但是忘记了另外存储旧值导致的！！！
  • dp[i][j] = 1 + min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])
  • 再遇到这样的得注意

打家劫舍

• 740. 删除并获得点数
  • 参考题解
• 对比使用[1][0]两个状态的，和一个状态的

Misc

• 2708.一个小组的最大实力值
  • 维护两个状态：最小乘积，最大乘积
  • 状态更新：不选当前元素、当前元素单独乘积、当前元素为负时✖️最小 -> 最大乘积、当前元素为正时✖️最大 -> 最大乘积；当前元素为负时✖️最大 -> 最小乘积、当前元素为正时✖️最小 -> 最小乘积

记忆化-> 动规

3177. 求出最长好子序列 II

• 容易想出记忆化搜索 -> 但是转化为动归有点难☹️
• 下次遇到记忆化搜索的，都尝试翻译成动态规划试一试

利用动规预处理数据，为后续计算做准备

• 2552. 统计上升四元组
  • 这题考虑遍历（j, k） -> 这里就么有想到
  • 创建二维数组mem -> 使用二维数组记录大小元素个数信息也没有想到
    • 有部分前缀和的思想在里面
  • 事先计算[x, y]范围里，比y小的元素数目 -> 记录到mem[x][y]
  • 计算[y, z]范围里，比y大的元素数目 -> 记录到mem[x][z]

股票问题大汇总

• 一套模板