动态规划问题思路与题型分类
基本思路
- 找到问题的状态（明确dp数组含义）（难点）
- 定义base case（填写数组边界值）
- 找到状态转移方程（难点）
- 填写dp数组
举例分析
先已知问题是动态规划找思路，再考虑如何判断属于动态规划
经典问题
背包问题
01背包
494. 目标和（组合问题）（装满背包）
474. 一和零（二维背包）
完全背包
518. 零钱兑换 II（装满背包）
377. 组合总和 Ⅳ（排列问题）（装满背包）（难）
背包问题的总结
打家劫舍问题
子序列问题
思路：
确定dp数组含义：子序列问题一般都是以nums[i]为结尾的{所求代入}
base case（边界）
状态转移方程：找dp[i]与dp[i-1]的关系，考虑dp[i-1]到dp[i]关于nums[i]有几种情况，再求这几种情况的最值
填表
股票买卖问题
编辑距离问题
技巧型题目
非典型，靠经验
动态规划的优化方法
空间压缩
dp[i]只与dp[i-1]有关，用一维数组代替二维数组，降低空间复杂度，要分清里层循环的方向
如何判断一个问题是动态规划
根据题目给定的参数范围
Reference
https://labuladong.gitee.io/algo/3/23/67/