代码随想录动态规划理论基础 Visualgo 动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划概念理解

从初始状态（起点）出发，经过一系列的状态转移（行进路线），到达目标状态（终点），求最优值/方案数/概率。

• 状态转移必须有方向，且不能成环
• 状态的个数需要在可接受范围内
• 复杂度：状态数量O(n^2) x 状态转移开销 O(n)= O(n^3)

状态 用数字精确描述的一个局面，对应问题的值。 f(i,j) -> dp[i][j]

• 飞行棋：f(Turn,Pos)=赢的概率
• 五子棋：f(Board)=是否必胜
• 魔方：f(Sticker)=最小还原步数

动态规划成立的前提条件：

• 状态转移 "无后效性"：将原问题分解成若干个子问题，每个子问题的求解过程作为一个阶段，当前阶段的求解只和当前阶段有关，与之后阶段无关。某阶段的状态一旦确定，就不受这个状态的后续决策影响。
• 状态与状态转移构成的图是有向无环图

状态转移（决策）

代码随想录

动态规划vs贪心算法

• 动态规划中每一个状态一定是==由上一个状态推导出来的==
• 贪心没有状态推导，而是从==局部直接选最优==的

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

• 动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
• 但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。 所以贪心解决不了动态规划的问题。

动态规划的解题步骤

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。 对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

动态规划五部曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式 (状态转移方程)
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

debug

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！ 做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

• 这道题目我举例推导状态转移公式了么？
• 我打印dp数组的日志了么？
• 打印出来了dp数组和我想的一样么？

Reference

代码随想录动态规划理论基础 Visualgo 动态规划 bilibili-动态规划讲解