我是怎么向5岁侄女解释动态规划的？

Myth丶恋晨 2023-01-11 13:13 107阅读 0赞

![format_png][]

“

dp dp dp dp ....

![format_png 1][]

我膨胀了，相信看了这个标题的同学，肯定忍不住破口大骂，什么瓜皮哦，dynamic programming这么简单吗，在我的印象里，尼玛动态规划是最难的。

> 背景

侄女5岁现在开始学习加减法了，每次做数学都离不开她的小手指，超过5的就开始数另一个手的手指，真是汗颜啊

有一天，我问她

“1+1+1+1+1等于多少？”

“搬起小拇指，就开始数了，5！”

“那么再加一个1呢？”

“当然是6了” -脱口而出

“这次你怎么算这么快的？”

“刚刚不是5吗，加1就是6了啊”

“所以你不需要重新计算，因为你记得之前的答案是5！动态规划就是说：记住之前的东西可以节省时间”

进入正题

玩归玩，闹归闹，别拿dp开玩笑！

来瞅一眼科普中国科学百科的词条解释

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

看不完的童鞋跳过，咱整点简单点的

其实刚刚这道题应该算是最简单的动态规划题目了。

我们可以看出这道题有什么特点呢？

我们知道之所以**最后一步**加1会计算的那么快，大部分要归功于之前计算过答案是5，如果我们把问题归纳为一个**子问题**，我想要计算每一步的答案，就可以列出一个方程：f(x) = f(x -1) + 1, 大家别对f(x)发怵，就把它当做一个简单的方法。

其中，f(x)为第几步的值，设定一个初始值，x > 0, 则第一步

f(1) = 1;

f(2) = 2;

...

f(6) = 6

在程序的世界里，用什么东东来存一个可以记录之前结果值的数据结构呢？

显而易见：**数组**呗。直接利用下标来存，巴适, 这就是动态规划里的动态，规划就是限定一些边界和初始化。

来个训练题

别看了，这也是一道简单的题

leecode 322: 你有三种硬币，2元、5元、7元，每种硬币足够多，买一本书需要27元，用最少的硬币组合

![format_png 2][]

怎么感觉像是回到了小学应用题？

\--简单分析一下： 最小硬币组合 -> 尽量用大的硬币

这傻不拉几的题谁出的，这么简单

7+7+7=21,21+2+2+2=27， 6枚硬币

卧槽

7+5+5+5+5=27， 5枚硬币

我们可以很暴力的想一想，从大往小的算，可以加起来不超过27，比如

7+7+7+7 > 27 (排除）

7+7+7+5 或者 7 +7 +7+2+2+2 6枚

....

穷举太慢了，还会涉及到很多的重复计算，如果我想要27以内的任何值最小的硬币组合呢，想想都头大了吧。

既然计算机可以通过内存保存之前的内容，又快，很明显，我们开一个数组来保存之前的状态。

**重点****预警**

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

简单的说，解动态规划的时候需要开一个数组，数组的每个元素f\[i\]或者f\[i\]\[j\]代表什么，类似数学题中x, y, z代表什么

解动态规划需要两个意识：

*  最后一步
 *  子问题

**最后一步**

刚刚第一题不是说了嘛，最后一步的计算结果是5。对于这道题，虽然我们不知道最优策略是什么，但是最优策略肯定是K枚硬币，a1, a2, ....ak面值加起来是27

所以一定有一枚最后的硬币:ak.

除掉这么硬币，前面硬币的面值加起来是27-ak

关键点1：

*  我们不关心前面的k-1枚硬币是怎么拼出27-ak的（可能有一种拼法，也可能有100种拼法），而且我们现在甚至还不知道ak和K, 但是我们确定前面的硬币拼出了27-ak

关键点2：

*  因为是最优策略， 所以拼出27-ak的硬币数一定要最少，否则这就不是最优策略了

![format_png 3][]

**子问题**

*  所以我们就要求：最少用多少枚硬币可以拼出27-ak
 *  原问题是最少用多少枚硬币拼出27
 *  我们将原问题转化了一个子问题，而且规模更小：27-ak
 *  为了简化定义， 我们设状态f(x）=最少用多少枚硬币拼出x

等等，我们还不知道最后的那枚硬币ak是多少

1.  很明显，最后的那枚硬币只能是2,5或者7
2.  如果ak是2， f(27)应该是f(27-2)+1(1代表最后一枚硬币2）
3.  如果ak是5， f(27)应该是f(27-5)+1(1代表最后一枚硬币5）
4.  如果ak是7， f(27)应该是f(27-7)+1(1代表最后一枚硬币7）

所以使用最少的硬币数=f(27) = min\{f(27-2)+1, f(27-5)+1, f(27-7)+1\}

1.2. 动态规划组成部分2：转移方程

设状态f(x)=最少用多少枚硬币拼出x

对于任意的x : f(X) = min\{f(X-2)+1, f(X-5)+1, f(X-7)+1\}

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

提出问题

1.  x-2, x-5, x-7 小于0怎么办？
2.  什么时候停下来？

1.3.1

如果不能拼出Y, 就定义f\[Y\] = 正无穷

例如f\[-1\], f\[-2\] = 正无穷

例如：拼不出f\[1\]=min\{f(-1)+1, f(-3)+1, f(-6)+1\}

初始条件：f\[0\] = 0

2.4. 动态规划组成部分2：计算顺序

计算：f\[1\], f\[2\], ... f\[27\]

当我们计算到f\[x\], f\[x-2\], f\[x-5\], f\[x-7\] 都已经得到结果了

如图：

![format_png 4][]

f\[x\] = 最少用多少枚硬币拼出x

f\[x\] = ∞ 表示无法用硬币拼出x

**参考代码**

public  static  int coinChange(int [] A, int M ) {
     int[] f = new int[M+1];
     int n = A.length;
     f[0] = 0;
     int i,j;
     for (i = 1; i<=M; i++) {
        f[i] = Integer.MAX_VALUE;
        for (j = 0; j< n;j++) {
            // 边界条件判断
            if (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {
                f[i] = Math.min(f[i - A[j]] + 1, f[i]);
              //  System.out.println(i + "=" +f[i]);
            }
        }
     }
     if (f[M] == Integer.MAX_VALUE) {
        f[M] = -1 ;
     }
     return  f[M];
    }

????

核心代码就4行，是不是很简单~

当然这道题也可以通过剪枝的方法实现，这里就不多赘述

再来个训练题

![format_png 5][]

![format_png 6][]

还是再来一题吧，一道题也太随意了~

leecode 62 ：不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

![format_png 7][]

看了上面的解题步骤，按部就班的来

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

**最后一步**

无论机器人用何种方式到达右下角，总有最后挪动的一步：-向右或者向下

如果所示，我们设右下角的坐标为(m-1,n-1)

那么最后一步的前一步机器人的位置在（m-2,n-1)或者(m-1,n-2)

**子问题**

那么，如果机器人有x种方式从左上角走到(m-2,n-1), 有Y种方式从左上角走到(m-1,n-2), 则机器人有X+Y的方式走到(m-1,n-1)

问题转化为，机器人有多少种 方式从左上角走到(m-2,n-1)或者(m-1,m-2）

如果走到是(m-2,n-1)如图：

![format_png 8][]

我们可以直接干掉最后一列

同理如果是走到(m-1,n-2)行就减少一行。

**状态**：

设f\[i\]\[j\]为机器人有多少种方式从左上角走到(i,j)

2.2. 动态规划组成部分2：转移方程

对于任意一个格子：

f\[i\]\[j\] = f\[i-1\]\[j\] + f\[i\]\[j-1\]

1          2            3

1代表机器人有多少种方式走到\[i\]\[j\]

2代表机器人有多少种方式走到f\[i-1\]\[j\]

3代表机器人有多少种方式走到f\[i\]\[j-1\]

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

初始条件：f\[0\]\[0\]=1,因为机器人只有一个方式到左上角

边界情况：i=0或j=0，则前一步只能有一个方向过来，也就是说第0行或者第0列，每走一步只有一种情况，则f\[i\]\[j\] = 1,其他区域都满足转移方程。

3.4. 动态规划组成部分4：计算顺序

按行计算，为什么按行计算呢？

对于这道题来说，按行计算在计算到f\[1\]\[1\]时，f\[0\]\[1\]和f\[1\]\[0\]都已经计算了，同样按列计算这两坐标也计算了，不用再次计算。

*  f\[0\]\[0\] =  1
 *  计算第0行：f\[0\]\[0\],f\[0\]\[1\],...,f\[0\]\[n-1\]
 *  计算第1行：f\[1\]\[0\],f\[1\]\[1\],...,f\[1\]\[n-1\]
 *  ...
 *  计算第m-1行：f\[m-1\]\[0\],f\[m-1\]\[1\],...,f\[m-1\]\[n-1\]

时间复杂度：O(mn)

![format_png 9][]

**参考代码**

public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        int i,j;
        for (i = 0; i<m; i++) {
            for (j = 0; j< n; j++) {
                if (i == 0 || j == 0) {
                    f[i][j] = 1;
                } else {
                    f[i][j] = f[i -1][j] + f[i][j-1];
                }
            }
        }
        return f[m-1][n-1];
    }

总结一下

什么题可以选择动态规划来做？

**1.计数**

*  有多少种方式走到右下角
 *  有多少种方法选出k个数是的和是sum

**2.求最大值最小值**

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

**3.求存在性**

*  取石子游戏,先手是否必胜
 *  能不能选出k个数使得和是sum

看到这里，基本上算是入门啦！

--------------------

![format_png 10][]

[format_png]: /images/20221119/f4752cddbb844b74946f56be3e41bae2.png
[format_png 1]: /images/20221119/8bbc7d3fcf75472396a121405b790980.png
[format_png 2]: /images/20221119/ea933a94b4a04541a61faa10c1ea21cc.png
[format_png 3]: /images/20221119/d8b74ac6da0542989c0ca966561b0794.png
[format_png 4]: /images/20221119/ab78873d4e7f40fa851d56e631d7bdc4.png
[format_png 5]: /images/20221119/8cee074e3008468c94c492313e0499f9.png
[format_png 6]: /images/20221119/ee3ed3240d6945d8aa22fae6062696fc.png
[format_png 7]: /images/20221119/f2c340cecbb84b31b27fc1dfd744975e.png
[format_png 8]: /images/20221119/a92ecd0356314e6ebb6c60d6b926c2fc.png
[format_png 9]: /images/20221119/6778d95baf324ffeaf1f6bb9ded82f8d.png
[format_png 10]: /images/20221119/b92b6dcf1a944c899462fa28b886e053.png