动态规划理论基础

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

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组（过程模拟）

509. 斐波那契数

确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

确定递推公式

题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：

dp[0] = 0;
dp[1] = 1;

确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

举例推导dp数组（后续省略）

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

class Solution:def fib(self, n: int) -> int:if n == 0:return 0dp = [0] * (n + 1)dp[0] = 0dp[1] = 1 # 初始值for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2] # 递推公式return dp[n]'''
class Solution:def fib(self, n: int) -> int:if n <= 1:return nprev1, prev2 = 0, 1for _ in range(2, n + 1):curr = prev1 + prev2prev1, prev2 = prev2, currreturn prev2
'''

递归实现

class Solution:def fib(self, n: int) -> int:if n < 2:return nreturn self.fib(n - 1) + self.fib(n - 2)

70. 爬楼梯

提取信息并转化：爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

确定dp数组以及下标的含义

dp[i]：爬到第i层楼梯，有dp[i]种方法

确定递推公式

如何可以推出dp[i]呢？从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。

dp数组如何初始化

dp[1] = 1，dp[2] = 2，这个初始化很容易可以得出。

确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2]中可以看出，遍历顺序一定是从前向后遍历的，这个题目的解法和上个题目几乎一样！

class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[1] = 1dp[2] = 2 # 初始值for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2] # 递推公式return dp[n]

746. 使用最小花费爬楼梯

确定dp数组以及下标的含义

使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

确定递推公式

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

dp数组如何初始化

初始化 dp[0] = 0，dp[1] = 0;

确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0] * (len(cost) + 1)dp[0] = 0dp[1] = 0for i in range(2, len(cost) + 1):dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[len(cost)]