vlambda博客
学习文章列表

豁然开朗经典算法之【动态规划】



何谓动态规划?

《算法导论》是这样解释动态规划的:动态规划与分治法相似,都是通过组合子问题的解来求解原问题答案,将问题划分为互不相交的子问题,递归的求解子问题,最后合并子问题的答案,得到原问题的答案。


翻译成人话就是:计算并存储小问题的解,并将这些解组合成大问题的解。






动态规划题目的解题思想

首先是将大问题进行拆分,动态规划题目我们可以把题目要求的解作为一个大的问题,然后对这个大问题进行划分,分成一步一步的可以通过递推或者递归实现的。这个小问题往往是一个值,这个值我们通常是用一维数组或者是二维数组来保存的

如果你成功将一个大问题拆分成了小问题,也就是说你已经知道了只有一种情况时最小结构的解是什么,那么你就可以以这个最小的结构为基础向上推导,进而得到一种不同层级解之间的关系。这有点像数学归纳法就是把你拆分的一步步之间的关系使用数学的推导公式来表示出来,这个公式用递归是很容易实现的。

最后既然动态规划要使用到递归,那么就不得不考虑边界问题了。所以边界问题也是动态规划必须考虑的。

所以总结一下,要想解决一个动态规划问题,下面的三要素是必须的:

  • 最优子结构,上文提到的拆分到的最小的那一步。

  • 边界 ,涉及到递归必须考虑的问题。

  • 状态转移方程 ,拆分过程中不同步之间的关系。

乍看之下,动态规划其实蛮暴力的,使用动态规划往往需要经过繁琐的计算,最后才一举解决问题,有点像武侠小说中经常看到的那种先蓄力在发动的绝招一样。但是解决动态规划问题是必须要注意的一点是,小问题的解一旦被计算出来,就要存储起来,不要重复计算,如果你忘了这一点,在实际的生产环境中,你的代码将会是服务器的灾难。动态规划运用得当,可以高效的解决问题。

下面我们就按照所说的三步来解决题目。




经典动态规划题:数字三角


题目描述


豁然开朗经典算法之【动态规划】

在上面的数字三角形中寻找一条从顶部到底部的路径,使路径上所经过的数字之和最大。路径上的每一步都只能往左下或者右下走,只需要求出这个最大的和即可,不必给出具体的路径。

要求:三角形的行数大于1小于等于100,数字为0-99。

输入格式如下:

5                      

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

第一行的5表示行数,其余的5行数据为三角形的组成数。

解题思路

第一步找最优子结构,把问题拆分


我们拿到这个题目,从题目中得到的关键信息:从顶部到底部,最大数字之和为什么这两个信息重要呢?"从顶部到底部"基本定格了我们找最优结构的方向,也就是从第N层开始。"最大数字之和"就是我们所说的“大问题”。所以我们要拆分的小问题就是这个基础值。


首先我们想第N层的节点值,N层三角形第N层肯定只有一个数值,一层的时候(用题目中的三角为例):

豁然开朗经典算法之【动态规划】

这个数组我们怎么表示呢?可以用一个一维数据D[i]表示。

那如果有两层呢?

    豁然开朗经典算法之【动态规划】

两层的时候就有两种路径,两个和,分别是7+37+8显然我们取两个值中的大的值作为最终解。这里发现一个问题,表示数值的大小不能用一维数组了,好是采用二维数组D[i][j](表示第i行第j个数字)。把当前的位置[i,j]看成一个状态,然后定义状态[i,j]的指标函数maxSum(i,j)为从位置[i,j]出发时能得到的最大和。

可以看出每走第i行第j列时有两种后续:向左下或者向右下。不同状态之间转移从[i,j]出发有两种决策。如果往左走,则走到[i+1,j],后需要求从[i+1,j]出发后能得到的最大和,即maxSum(i+1,j)。往右走之后需要求解maxSum(i+1,j+1)。由于可以在这两个决策中自由选择,所以应选择maxSum(i+1,j)和maxSum(i+1,j+1)中较大的一个。由此到如下状态转移方程:

maxSum(i,j) = D(i,j) + max{maxSum(i+1,j),maxSum(i+1,j+1)}

因为最后一行可以确定,所以当做边界我们需要求解的是maxSum(1, 1),所以上题的递归大概是这个样子:

if(i == N)    maxSum(i,j) = D[i][j]else    maxSum(i, j) = Max{maxSum(i+1, j), maxSum(i, j+1)} + D[i][j]

所以上面问题的核心实现JAVA版:

public int getMax(){ int MAX = 101; //存储数字三角形 int[][] D = new int[MAX][MAX];  //n表示层数 int n;  int i = 0; int j = 0; int maxSum = getMaxSum(D,n,i,j); return maxSum; } public int getMaxSum(int[][] D,int n,int i,int j){ if(i == n){ return D[i][j]; } int x = getMaxSum(D,n,i+1,j); int y = getMaxSum(D,n,i+1,j+1); return Math.max(x,y)+D[i][j];  }

更简单的写法:

return D[i][j]+(i==n? 0 : max(maxSum(i+1,j),maxSum(i+1,j+1)));

标准AC的答案,在这C语言版本

#include <iostream>#include <algorithm>#define MAX 101
use namespace std;int D[MAX][MAX];int n;
int maxSum(int i, int j){ if(i == N){ return D[i][j]; } int x = maxSum(i + 1, j); int y = maxSum(i + 1, j + 1); return max(x, y) + D[i][j];}
int main(){ int i, j; cin >> n; for(i = 1; i <= N; ++i){ for(j = 1; j <= i; ++j) cin >> D[i][j]; } cout << maxSum(1, 1) << endl;}

 你以为这样就结束了吗?你想过上面算法的时间复杂度了吗?举个例子说明上面递归的流程,示例:

豁然开朗经典算法之【动态规划】

按照上面的递归这个例子的调用流程如下:

豁然开朗经典算法之【动态规划】

由此可见这个算法的时间复杂度是2^N

这样递归是正确的,但时间效率太低,其原因在于重复计算。在MAX(1,1)对应的调用关系树中,MAX(3,2)被计算了两次(一次是MAX(2,1)需要的,一次是MAX(2,2)需要的)。也许读者会认为重复算一两个数没有太大影响,但事实是:这样的重复不是单个结点,而是一颗子树。如果原来的三角形有n层,则调用关系树也会有n层,一共有2^n-1个结点。

现在思考一下,如果每算出一个MaxSum(r,j)就保存起来,下次用到其值的时候直接取用,就可以免去重复计算。那么 可以用O(n2)时间完成计算。因为三角形的数字总 数是 n(n+1)/2


记忆性动规实现



#include<iostream>#include<algorithm>using namespace std;#define MAX 101int D[MAX][MAX];int n;int maxSum[MAX][MAX];
int MaxSum(int i,int j){ if(maxSum[i][j] != -1)//这个数字的最大值已经被求出来了 return maxSum[i][j]; if(i == n)//如果i==n,那就说明它已经是最后一行的那个数字了, 那最大和就是那个数字它自己 maxSum[i][j] = D[i][j]; else //否则呢,我们就要算一下 它正下方的那个数字走到底边得到的最大和是什么 { int x = MaxSum(i + 1, j); int y = MaxSum(i + 1, j + 1); maxSum[i][j] = max(x,y) + D[i][j]; } return maxSum[i][j];}
int main(){ int i,j; cin >> n; for(i = 1 ; i <= n ; i++) for(j = 1 ; j <= i; j++) { cin >> D[i][j]; maxSum[i][j] = -1; } cout << MaxSum(1,1) << endl;}

时间复杂度就变成了O(n^2)因为这个数字三角形里面数字的总数是n(n+1)再除以2,对于每一个数字 它到底边的最大和都只需要算一次就行了。那这样需要算的总的次数就是这么多。时间复杂度就是n^2了。


这是一种减少时间复杂度的方法,当然动态规划的问题也可以把递归转换成递推的方式,可以减少空间复杂度,感兴趣的可以网上找找对应的实现。




小结

解决动态规划的一般思路:

1、将原问题分解为子问题

2、确定各个子问题之间的关系,能够写出状态转移方程。

3、确定边界

动态规划的适用场景:

1、问题具有最优子结构性质。

2、无后效性。当前的若干个状态值一旦确定,则此后过程 的演变就只和这若干个状态的值有关,和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。

说白了就是一般遇到求最优解问题一般适合使用动态规划













cizikeshafd

豁然开朗经典算法之【动态规划】
豁然开朗经典算法之【动态规划】
豁然开朗经典算法之【动态规划】


小码逆袭

求撩!
有用请给我”素质三连“哦,感谢🙏