当前位置:首页 > 算法 > 正文内容

【算法】动态规划(二)——数字三角形问题

亿万年的星光4年前 (2021-05-28)算法3371

1.问题描述及状态定义

数字三角形问题:有一个非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示:

从第一行开的数开始走,每次可以往下或右走一格,直到走到最下行,把沿途经过的数全部加起来。如何走才能使得这个和最大?

2.尝试找到最优解

我们可以先尝试找找看,能不能找到最优解,也就是找到最大的那个和是多少。

第一条路:1,3,4,4 和是12

第二条路:1,3,10,3 和是17

第三条路:1,2,1,10 和是14

.......

在这里我们基本找到了最大的和。回过头来想一个问题, 是不是贪心?。

很显然,不是贪心,我们在这个过程中,无法按照某一个特定的策略找到最大值。比如下面这张图:

如果,我们按照贪心策略,在每一层都选最大的,那面我的选择一定是1,3,10,3。而不是1,2,9,10。所以,动态规划问题不是贪心问题,区别在于这是一个动态的决策过程。


3.分析

    如果熟悉回溯法,可以看出这是一个动态的过程——每次有两种选择——左下或右上。如果用回溯法求出所有可能的录像,就可以从中选出最优路线。但是回溯法的效率太低:一个n层数字三角形的完整线路有2n-1条,当n很大时回溯法不再适用。

    为了得到更高效的算法,需要用抽象的方法思考问题:把当前的位置(i,j)看出一个状态,然后定义状态(i,j)的函数d(i,j)。其含义为从格子(i,j)出发时能得到的最大和(包括格子(i,j)本身的值)。可以用下面带编号的图辅助理解。

    根据上面画的辅助图,我们看看不同状态之间是如何转移的。

    从格子(i,j)出发有量两种决策。如果往左走则是(i+1,j),后需要求 从“(i+1,j)出发后得到的最大和“这一问题,即d(i+1,j)。

    如果是忘右走,需要求解 从 d(i+1,j+1)。

    由于可以在这两个决策中自由选择,所以应该选择d(i+1,j)和d(i+1,j+1)中较大的一个。换句话说,我们得到了所谓的状态转移方程

    d(i,j) =a(i,j)+max{ d(i+1,j), d(i+1,j+1)}

    如果往左走,那么最好情况等于(i,j)格子里的值a(i,j)与”从(i+1,j)出发的最大总和“之和,此时需要注意这里的”最大“二字。如果连”从(i+1,j)出发走到底部“这部分的和都不是最大的,加上a(i,j)之后肯定也不是最大。这个性质称为”最优子结构“,也可以描述为”全局最优解包含局部最优解“。

    状态和状态转移方程一起完整地描述了具体的算法。


3.关于动态规划中“自底向上”的理解

在动态规划中,解题步骤中一般要求“自底向上”求解。什么是“自底向上”求解。还是拿上面的图举例。

在上面的分析中,我们从最顶点开始考虑,然后递归到底部求解得出结论。自底向上求解就是从最底部开始,两者当中取较大者往上加。比如,最后一层到倒数第二层的结果是:

在最后一层中,4和3比较,4比较大,所以选4,到了上一层加上原来的4就变成8。同理,3和2比较,3比较大,到了上面一层加上原来的10变成13。2和10比较10比较大,加上原来的9变成19。

然后继续往上走。

然后8和13比较,13比较大,到上一层变成16,13和19比较19比较大。到上一层变成21。最大值22。最大值路径还是跟原来一样。

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【算法】高精度(2)

五、高精度处理进位与借位    其实也很简单,我们再来模拟一下,1439+887的时候,首先我们最低位相加,得到16,那么答案最低位就是6,再进个1,然后两数的十位相加,...

【贪心】 导弹拦截

【贪心】 导弹拦截

【题目描述】某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统,但是这种拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来...

【算法】动态规划(三)——解题方法与解题思路

0.前言动态规划最核心的思想就是:拆分子问题,记住过往,减少重复计算。动态规划可以从下面的参考网上的一个例子:A :"1+1+1+1+1+1+1+1 =?"...

【二分】----基础用法

【二分】----基础用法

0.二分法简介二分法是一种查找算法要求:数据必须是有序序列核心思想:掐头去尾取中间1. 引入对于一个有序数组,如{1,3,6,8,23,56,78,99},如果我们要查找其中的一个数78的下标位置,按...

【排序】----插入排序

【排序】----插入排序

1.基本思想在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。2.过程·(1)从第一个元素开始,该元素可以...

【贪心】----最优装载、背包、乘船问题

【贪心】----最优装载、背包、乘船问题

1.最优装载题目描述:有n个物体,第i个物体的重量为wi(wi为正整数)。选择尽量多的物体,使得总重量不超过C。【分析】由于只关心选择的物品的最大数量(而不是最大重量,最大重量需要考虑DP),所以装重...