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

一时失言乱红尘 2023-01-20 06:55 85阅读 0赞

首先,我们看一下官方定义:  
**定义:**  
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。  
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。  
**基本思想与策略编辑:**  
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。  
*(来自百度百科)*  
说实话,没有动态规划的基础很难看懂,但是也能从中看出一些信息,下面我翻译成**人话**:  
**首先是拆分问题**,我的理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现.  
关键就是这个步骤,动态规划有一类问题就是从后往前推到,有时候我们很容易知道:**如果只有一种情况时,最佳的选择应该怎么做**.然后根据这个最佳选择往前一步推导,得到前一步的最佳选择  
**然后就是定义问题状态和状态之间的关系**,我的理解是前面拆分的步骤之间的关系,用一种**量化的形式**表现出来,类似于高中学的推导公式,因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态转移方程式)  
**我们再来看定义的下面的两段**,我的理解是比如我们找到最优解,我们应该讲最优解保存下来,为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解,此时我们应该放弃,**只保存最优解**,这样我们每一次都把最优解保存了下来,大大降低了时间复杂度

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

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

题目:![题目描述][70]  
![输入格式][70 1]  
可以看出每走第n行第m列时有两种后续:**向下或者向右下**  
由于最后一行可以确定,当做边界条件,所以我们自然而然想到递归求解  
解题思路:![解题思路][70 2]  
![c语言答案][c]  
下面简单写一下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

其实仔细观察,上面的解答过程时间复杂度难以想象的大,那是因为他对有的数字的解进行了多次的重复计算,具体如下图:  
![超时原因][70 3]  
如果不明白上图,可以把每条路径都画出来,观察每个数字有多少条路径经过了他,就会一目了然  
然后我们就可以自然而然的想到,如果我们每次都把结果保存下来,复杂度就会大大降低  
![改进方法][70 4]  
其实答案很简单:![改进解法][70 5]  
其实这是动态规划很精髓的一部分,是减少复杂度的主要原因  
我们都知道,递归一般情况下是可以转化为递推的,不详细解释了,贴上答案:  
![递推解法][70 6]  
其实,仔细观察该解题过程,该过程就是标准的动态规划解题过程,如果把该过程画出来(找到每一步的最优解,其他的舍弃)对动态规划会有更深刻的解法  
还有就是,递推的另一个好处是可以进行空间优化,如图:  
![空间优化][70 7]  
下面总结一下动态规划的解题一般思路:  
首先递归应该是我们解决动态规划问题最常用的方法,帅,速度不算太慢  
**那么递归到动规的一般转化方法为:**  
如果该递归函数有n个参数,那么就定义一个n维数组,数组下标是递归函数参数的取值范围(也就是数组每一维的大小).数组元素的值就是递归函数的返回值(初始化为一个标志值,表明还未被填充),这样就可以从边界值开始逐步的填充数组,相当于计算递归函数的逆过程(这和前面所说的推导过程应该是相同的).  
原文链接:https://blog.csdn.net/ailaojie/article/details/83014821

动规解题的一般思路(标准官方,不过经过前边讲解应该就能理解了):

1.  **将原问题分解为子问题**(开头已经介绍了怎么分解) (**注意**:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了; 2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)
2.  **确定状态**(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间".我的理解就是状态就是某个问题某组变量,状态空间就是该问题的所有组变量) **另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间**
3.  确定一些初始状态(边界条件)的值 (这个视情况而定,千万别以为就是最简单的那个子问题解,上面只是例子,真正实践动规千变万化)
4.  确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推,由已知推未知)

适合使用动规求解的问题:  
1,问题具有最优子结构  
2,无后效性 说的花里胡哨的,其实一般遇到求最优解问题一般适合使用动态规划

部分参考资料出自：北大信科郭炜老师

[70]: /images/20221021/85fbd71f71524f3ead0cc5b89e7e765e.png
[70 1]: /images/20221021/06ee2d953eda429b85c16aa6357f4466.png
[70 2]: /images/20221021/718863c55b864be6839b9572d95271b3.png
[c]: /images/20221021/3b7849313c3f46d58174db51e94345b5.png
[70 3]: /images/20221021/344478b8577d4e6ea94de52a9e6d429b.png
[70 4]: /images/20221021/b454641840c14bfeb74666b66c4c79fb.png
[70 5]: /images/20221021/9b795666607e4a21a706c5e03cf2e5f1.png
[70 6]: /images/20221021/383b7d7244ea470cb305a40b58867997.png
[70 7]: /images/20221021/f981b0814e1e4ee48c6f2519e28cc809.png