oskycar / leetcode / 狂刷100道题,我是怎么向5岁侄女解释动态...

分享

   

狂刷100道题,我是怎么向5岁侄女解释动态规划的? | 掘金年度征文

2021-02-22  oskycar

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

背景

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

有一天,我问她

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

“搬起小拇指,就开始数了,5!”

“那么再加一个1呢?”

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

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

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

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

进入正题

\color{red}{玩归玩,闹归闹,别拿dp开玩笑!}玩归玩,闹归闹,别拿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

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

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

来个训练题

\color{red}{别看了,这也是一道简单的题}别看了,这也是一道简单的题

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

img

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

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

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

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的硬币数一定要最少,否则这就不是最优策略了

img

子问题

  • 所以我们就要求:最少用多少枚硬币可以拼出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] 都已经得到结果了

如图:

img

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];
}
复制代码

😄

\color{red}{核心代码就4行,是不是很简单~}核心代码就4行,是不是很简单 

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

再来个训练题

img

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

leecode 62 :不同路径

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

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

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

img

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

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)如图:

img

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

同理如果是走到(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)

img

参考代码

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

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>