经典中的经典算法:动态规划(详细解释,从入门至实践,逐步讲解)

由于动态规划解决的难题多数有重叠子问题这个特征递归算法经典实例，为避免重复计算递归算法经典实例，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

(来自百度百科)

说实话,没有动态规划的基础很难看懂,但是也可从中看出一些信息,下面我翻译话:

首先是拆分问题,我的理解就是根据问题的可能性把难题划分成一步一步这样就可以借助递推或者递归来实现.

关键就是这个方法,动态规划有一类问题就是从后向前推至,有时候我们很容易知道:如果只有一种情况时,最佳的选取需要怎样做.然后按照这个最佳选择往前一步推导,得到前一步的最佳选择

然后就是定义问题状况跟状态之间的关系,我的理解是中间拆分的方法之间的关系,用一种量化的方式体现出来,类似于高中学的推论公式,因为这些方程很容易用程序写下来,也可以说对程序非常亲跟(也就是最后所说的状况转移方程式)

我们再来看定义的以下的两段,我的理解是除了我们找到最优解,我们必须讲最优解保存下去,为了往后推导时才会使用前一步的最优解,在这个过程中常常有一些相比于最优解差的解,此时我们必须舍弃,只保存最优解,这样我们每一次都把最优解保存了出来,大大降低了时间复杂度

说很难理解清楚,容易懵懵懂懂的,所以以下结合实例看一下(建议结合实例,纸上谈兵不太好):

经典的数字三角形问题(简单易懂,经典动态规划);

题目:

可以看出每走第n行第m列时有两种后续:向下或者向右下

由于最终一行可以确认,当做边界条件,所以我们自然而然想到递归求解

解题思路:

下面简单写一下java代码:

//java代码纯属自己练习,标准答案参考上面的c语言答案

class solution{

public int getMax(){

int MAX = 101;

int[][] D = new int[MAX][MAX];//存储数字三角形

int n; //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];

}

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

其实仔细观察,上面的解答过程时间复杂度难以想像的大,那是因为他对有的数字的解进行了多次的重复计算,具体如下图:

如果不明白上图,可以把每条路径都画下来,观察每个数字有多少条路径经过了他,就会一目了然

然后我们就可以自然而然的想起,如果我们经常都把结果保存下去,复杂度就会大大降低

其实答案很简单:

其实这是动态规划很精髓的一部分,是降低复杂度的主要因素

我们都清楚,递归一般状况下是可以转换为递推的,不具体解释了,贴上答案:

其实,仔细观察该解题过程,该过程就是标准的动态规划解题过程,如果把该过程画下来(找到每一步的最优解,其他的放弃)对动态规划会有很深刻的解法

还有就是,递推的另一个好处是可以进行空间优化,如图:

下面总结一下动态规划的解题一般模式:

首先递归应该是我们解决动态规划问题更常见的方式,帅,速度不算很慢

那么递归到动规的通常转换方式为:

如果该递归函数有n个参数,那么就定义一个n维变量,数组下标是递归函数参数的取值范围(也就是数组每一维的大小).数组元素的值就是递归函数的返回值(初始化为一个标志值,表明还已被填充),这样就可以从边界值开始逐渐的填充数组,相当于计算递归函数的逆过程(这跟上面所说的推断过程需要是同样的).

原文链接:

动规解题的通常模式(标准官方,不过经过中间讲解应该能够理解了):

将原问题分解为子问题(开头已经介绍了如何分解) (注意:1,子问题与原问题方式相似或类似,只是问题规模变小了,从而变简单了;2,子问题即使求出就要保存下去,保证每个子问题只求解一遍)

确定状态(状态:在动规解题中,我们将跟子问题相关的各个函数的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状况的值,这个就是状态所对应的子问题的解,所有状况的集合称为"状态空间".我的理解就是状态就是某个难题某组变量,状态空间就是该难题的所有组变量)另外:整个问题的时间复杂度就是状态数量乘以每个状况所必须的时间

确定一些初始状况(边界条件)的值(这个视状况而定,千万别以为就是最简单的哪个子问题解,上面也是例证,真正实践动规千变万化)

确定状态转移方程 (这一步和第三步是很关键的 记住"人人为我"递推,由已知推未知)

适合使用动规求解的问题:

1,问题具有更优子结构

2,无后效性 说的花里胡哨的,其实通常见到求最优解问题大概适合使用动态规划

感觉自己洋洋洒洒写了几个小时,对动态规划有了一定的理解,也期望对他们有所帮助,动态规划千变万化,这只是是一个理解过程,我们还是需要多练习,共勉吧.转载的话,如果方便请加上转载地址,谢谢.

————————————————

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-136147-1.html