一 、动态规划做题套路总结：

• dp[] 数组的维度
• dp[i] 代表的含义是什么
• 最终的结果是 dp[n] 还是 fun( dp[] ) ，也就是要对dp数组做一个函数，如取dp数组中的最大值max dp[]
• 弄清楚状态转移方程

  常见的转移方程
  dp[i] = dp[i - 1] , dp[i - 2]
  dp[i] = dp[i - j] , !dp[i - j]
  etc

• 实在不行，就先列出dp数组的前几项，然后找规律

二、做过的题目总结

建议按顺序尝试

简单动态规划
53 最大子序和
746 使用最小花费爬楼梯
1025 除数博弈
70 爬楼梯

中等动态规划
650 只有两个键的键盘
剑指offer63 股票的最大利润
198 打家劫舍
221 最大正方形
931 下降路径最小和
14 14- I. 剪绳子
62 不同路径

高难动态规划
32 最长有效括号

三、动态规划优化：

1. 从前往后，避免递归
2. 空间优化，滚动数组 或者 常数级变量

四、目前还不太会的动态规划

1. 多维的动态规划，一看就很烦

   例题 有哪些

2. 有的不明所以，不知道 dp[][] 应该代表什么

   例题有

3. 有的不会写状态方程

   例题有

五、对于 动态规划 的一些有利于理解的文章