动态规划笔记

什么问题可以用动态规划求解计数求最大最小值求存在性 例题1 硬币组合问题动态规划组成部分一：确定状态子问题简介递归解法递归的问题 动态规划组成部分二：转移方程动态规划组成部分三：初始条件和边界情况小结

什么问题可以用动态规划求解

计数

有多少种方式走到右下角有多少种方法选出k个数使得和是Sum

求最大最小值

从左上角走到右下角路径的最大数字和最长上升子序列长度

求存在性

取石子游戏，先手是否必胜能否选出k个数使得和是Sum

例题1 硬币组合问题

Lintcode 669 想法1 尽量用大的硬币 结果是：7 + 7 + 7 = 21 ，21 + 2 + 2 + 2 = 27，共6枚硬币 正确答案：7 + 5 + 5 + 5 + 5 = 27，5枚硬币

动态规划组成部分一：确定状态

状态在动态规划中的作用属于定海神针动态规划需要开一个数组，数组的每个元素 f [ i ] 或者 f [ i ][ j ] 代表什么 – 类似于解数学题中的 X，Y，Z代表什么确定状态需要两个意识 – 最后一步 – 子问题

对于例题1，

虽然我们不知道最优策略是什么，但最优策略一定是K枚硬币a₁,a₂,…,a_k,加起来面值是27一定有一枚最后的硬币：a_k除掉这枚硬币，前面硬币的面值加起来是27 - a_k

关键点1：我们不关心前面的k-1枚硬币是如何拼出27 - a_k 的（或有1种拼法或100种），而且甚至现在不知道 a_k 和k，但我们确定前面的硬币频出了27 - a_k 。

关键点2：因为是最优策略，所以拼出27 - a_k 的硬币数量一定要最少。

子问题

简介

所以我们就要求：最少用多少枚硬币可以拼出27 - a_k原问题是最少用几枚硬币拼出27我们将原问题转换成了一个子问题，而且规模更小：27 - a_k为了简化定义，我们设状态 $f(x)$ 表示：最少用几枚硬币拼出X

只要找到子问题，就可以用动态规划求解，如何确定状态十分重要

我们还不知道最后那枚 a_k 是多少？

最后那枚 a_k 只可能是2，5或者7

如果 a_k 是2，$f(27)$应该是 $f(27-2)$ + 1 （加上最后这枚硬币2）

如果 a_k 是5，$f(27)$应该是 $f(27-5)$ + 1 （加上最后这枚硬币5）

如果 a_k 是7，$f(27)$应该是 $f(27-7)$ + 1 （加上最后这枚硬币7）

除此之外没有其他可能

新要求最少的硬币数，所以： $f(27)=min(f(27-2)+1,f(27-5)+1,f(27-7)+1)$

递归解法

递归的问题

这样的递归会导致有些节点被重新计算，时间复杂度过高，如图中的红色节点

做了很多重复计算，效率低下如何避免？将计算结果保存下来，并且改变计算顺序

动态规划组成部分二：转移方程

设状态$f(X)$ 最少用多少枚硬币拼出x对于任意X，有 $f(X)=min(f(X-2)+1,f(X-5)+1,f(X-7)+1)$

动态规划组成部分三：初始条件和边界情况

$f(27)=min(f(27-2)+1,f(27-5)+1,f(27-7)+1)$两个问题：X - 2 和 X - 5 或者 X - 7 小于0怎么办？什么时候停下来？如果不能拼出Y，就定义 $f(Y)=$ $+\infty$ 表示失败 – 比如 $f(-1)=f(-2)=...=$ $+\infty$所以 $f(1)=min(f(-1)+1,f(-4)+1,f(-6)+1)=$ $+\infty$初始条件：$f(0)=0$ 初始条件是用转移方程算不出来，且需要手工定义的，$f(0)$不应该为 $+\infty$，这样才有$f(2)=1$ #动态规划组成部分四：计算顺序拼出X所需要的最少硬币数： $f(X)=min(f(X-2)+1,f(X-5)+1,f(X-7)+1)$初始条件：$f(0)=0$然后计算$f(1),f(2),...,f(27)$当我们计算到$f(X)$时，$f(X-2)+1,f(X-5)+1,f(X-7)+1$都已经有结果了

小结

动态规划组成部分： -1. 确定状态

List item最后一步（最优策略中使用的最后一枚硬币）化成子问题（最少的硬币拼出更小的面值27- a_k)

-2. 转移方程

$f(X)=min(f(X-2)+1,f(X-5)+1,f(X-7)+1)$

-3.初始条件和边界情况

$f(0)=0$ ，如果不能拼出Y，$f(Y)=$ $+\infty$

-4.计算顺序

$f(0)，f(1) ，f(2) ，… $ public int coinChange(int[] A, int M) { int[] f = new int[M+1]; int n = A.length; //number of kinds of coins //initializtion f[0] = 0; int i, j; // f[1], f[2], ..., f[27] for (i = 1; i<= M; ++i) { f[i] = Interger.MAX_VALUE; // last coin A[j] // f[i] = min{ f[i-A[0]]+1, f[i-A[1]]+2,.., f[i-A[n-1]]+1 } for (j = 0; j < n; ++j) { if (i >= A[j] && f[i - A[j]] != Interger.MAX_VALUE) { f[i] = Math.min(f[i - A[j]] + 1, f[i]); } } } if ( f[M] == Interger.MAX_VALUE) { f[M] = -1; } return f[M]; }

---

笔记内容出自视频：https://www.bilibili.com/video/BV1xb411e7ww?from=search&seid=6650948173443064939