介绍
定义
动态规划时一种运筹学方法，是在多轮决策过程中的最优方法。
应用场景
动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
核心
求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。
动态规划特点（三要素）
1.最优子结构：原问题的最优解所包含的子问题的解也是最优的，通过子问题的最值得到原问题的最值。
2.存在重叠子问题：子问题间不独立（这是动态规划区别于分治的最大不同）；如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算
3.无后效性：即后续的结果不会影响当前结果。
通常的思考过程
动态规划没有标准的解题方法，但在宏观上有通用的方法论：
下面的 k 表示多轮决策的第 k 轮
1.分阶段，将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段，它们可以是不满足独立性的。
2.找状态，选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变，更像是决策可能的结果。
3.做决策，确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作，例如 D2 的可能的决策动作是 D2 -> E2 和 D2 -> E3。
4.状态转移方程。这个步骤是动态规划最重要的核心，即 sk+1= uk(sk) 。
5.定目标。写出代表多轮决策目标的指标函数 Vk,n。
6.寻找终止条件。
状态转移方程一般过程
状态转移方程：一般思考过程，明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。方程本质是数学的递推式
解题方法
递归是一种自顶向下的求解方式，DP数组是一种自底向上的求解方式。
1.递归寻找暴力解：自顶向下求解；
2.通过备忘录memo优化递归过程，剔除重复计算，消除一下重叠子问题；
3.通过DP table 自底向上求解：主要是需要明确DP数组的含义定义，然后通过递推进行推导。
DP数组注意事项
数组的遍历方向
# 正向遍历 int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) // 计算 dp[i][j] # 反向遍历 for (int i = m - 1; i >= 0; i--) for (int j = n - 1; j >= 0; j--) // 计算 dp[i][j] # 斜向遍历 for (int l = 2; l <= n; l++) for (int i = 0; i <= n - l; i++) int j = l + i - 1; // 计算 dp[i][j]
DP数组的递推计算过程需要注意两点：
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置
主要就是看 base case 和最终结果的存储位置。
如：编辑距离问题：正向遍历
回文子序列问题：从左至右斜着遍历，或从下向上从左到右遍历，都可以
举例
1.斐波拉契数列
暴力递归：时间复杂度2^n指数级
def fib(n): if n <= 2: return 1 return fib(n-1) + fib(n-2)
带备忘录的递归
def fib(n): def helper(n): if n <= 2: return 1 if n in memo: return memo[n] memo[n] = fib(n-1) + fib(n-2) return memo[n] memo = {} # 记录已经计算过的值，防止重复计算 return helper(n)
DP数组的迭代解法
上述递归过程是自顶向下求解的，dp数组则是自底向上求解的。
def fib(n): dp = [0 for _ in range(n+1)] dp[1] = dp[2] = 1 for i in range(3, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]
根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
def fib(n): if n <= 2: return 1 prev = 1 curr = 1 for i in range(3,n+1): prev, curr = curr, prev + curr return curr
2.零钱兑换问题
题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
状态转移方程：
# 伪码框架 def coinChange(coins: List[int], amount: int): # 定义：要凑出金额 n，至少要 dp(n) 个硬币 def dp(n): # 做选择，选择需要硬币最少的那个结果 for coin in coins: res = min(res, 1 + dp(n - coin)) return res # 我们要求的问题是 dp(amount) return dp(amount)
实际代码：
暴力解法
def coinChange(coins, amount): def dp(n): # 函数定义为目标金额为n时，所需的最少硬币数量 # base case # 目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1 if n == 0: return 0 if n < 0: return -1 # 求最小值，所以初始化结果为正无穷 res = float('inf') for coin in coins: subpro = dp(n-coin) if subpro == -1: # 子问题无解，跳过 continue res = min(res, 1 + subpro) return res if res != float('inf') else -1 return dp(amount)
带备忘录的递归
def coinChange(coins, amount): def dp(n): # 函数定义为目标金额为n时，所需的最少硬币数量 # base case # 目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1 if n == 0: return 0 if n < 0: return -1 if n in memo: return memo[n] # 求最小值，所以初始化结果为正无穷 res = float('inf') for coin in coins: subpro = dp(n-coin) if subpro == -1: # 子问题无解，跳过 continue res = min(res, 1 + subpro) memo[n] = res if res != float('inf') else -1 return memo[n] memo = {} return dp(amount)
DP数组迭代解法
dp[i] = x 表示，当目标金额为 i 时，至少需要 x 枚硬币。
def coinChange(coins, amount): # 数组大小为 amount + 1，初始值也为 amount + 1 # 因为总的零钱个数不会超过amount,所以初始化amount + 1即可 dp = [amount + 1 for _ in (amount + 1)] dp[0] = 0 for i in range(len(dp)): # 内层 for循环，求解的是所有子问题 + 1 的最小值 for coin in coins: # 子问题无解，跳过 if i - coin < 0: continue dp[i] = min(dp[i],1+dp[i-coin]) if dp[amount] == amount + 1: return -1 else: return dp[amount]
注：dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。
这个题目相当于是组合问题，每个硬币可以用多次，一共有多少种组合。
说明：前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。说的更加直白一点，那就是用前k的硬币凑齐金额i，要分为两种情况开率，一种是没有用前k-1个硬币就凑齐了，一种是前面已经凑到了i-k，现在就差第k个硬币了。
DP[i] = DP[i] + DP[i-k]:
式子右边的DP[i]表示不使用第K个金币的和为i的组合, DP[i-k]表示使用金币k的和为i的组合数。
第 39 题问的是所有的组合列表，需要知道每一个组合是什么？，应该使用 回溯算法 求解，并且存储每一个组合；
第 518 题问的是组合有多少种，而不是问具体的解。应该使用 动态规划 求解
class Solution: def change(self, amount: int, coins: List[int]) -> int: # 子问题:对于硬币从0到k，我们必须使用第k个硬币的时候，当前金额的组合数 # 状态数组DP[i]表示对于第k个硬币能凑的组合数 # 转移方程DP[i] = DP[i] + DP[i-k] dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for x in range(1, amount + 1): if x < coin: continue # coin不能大于amount dp[x] += dp[x - coin] return dp[amount]
这个题实际上是排列问题，因为顺序不同的话视为不同的组合。
class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0] * (target + 1) dp[0] = 1 for x in range(1, target + 1): for num in nums: if x < num:continue dp[x] += dp[x - num] return dp[target]
参考：
https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/
总结：
518零钱兑换2是一个组合问题，DP先遍历零钱列表，再遍历amount金额数；
def change(coins,amount): # 求的是组合数 dp = [0 for _ in range(amount+1)] dp[0] = 1 for coin in coins: # 枚举硬币 for i in range(amount + 1): # 枚举金额 if i < coin: continue #coin不能大于amount dp[i] = dp[i] + dp[i - coin] return dp[amount]
377组合个数是一个排列问题， DP先遍历amount金额数，再遍历零钱列表。
def change(coins,amount): # 求的是排列数 dp = [0 for _ in range(amount+1)] dp[0] = 1 for i in range(amount + 1): # 枚举金额 for coin in coins: #枚举硬币 if i < coin: continue #coin不能大于amount dp[i] = dp[i] + dp[i - coin] return dp[amount]
举例：
在LeetCode上有两道题目非常类似，分别是
70.爬楼梯 --排列问题
518. 零钱兑换 II -- 组合问题
如果我们把每次可走步数/零钱面额限制为[1,2], 把楼梯高度/总金额限制为3. 那么这两道题目就可以抽象成"给定[1,2], 求组合成3的组合数和排列数"。
爬台阶问题通用模板
def climbStairs(n): # 爬台阶问题通用模板 dp = [0 for _ in range(n + 1)] dp[0] = 1 steps = [1,2,4,5] for i in range(n+1): for j in range(len(steps)): if i < steps[j]: continue # 台阶少于跨越的步数 dp[i] = dp[i] + dp[i-steps[j]] return dp[n]
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（2）https://developer.aliyun.com/article/1536619
