背景

动态规划作为大厂算法常考题型，是每一位优秀程序员必备的知识技能，尽管她真的很难。

解题思路

一是确定DP状态，二是确定DP转移方程。

DP状态

DP状态，定义某一阶段的最优解，具备两个特征；

• 最优子结构：当前问题的最优解，可以从更小规模的子问题的最优解推导而来；
• 无后效性：只关心子问题的最优解，不关心该最优解的由来；

DP转移方程

定义DP状态后，再通过推导的方式写出转移方程；

小结

以斐波那契数列为例，0 1 1 2 3 5 ... 那么：

• DP状态：dp[i]指数组下标为i的值；
• DP转移方程：dp[i] = dp[i - 2] + dp[i - 1];

实战

• 打家劫舍
• 走方格
• 买卖股票
• 最长序列

参考链接

• 如何理解动态规划？