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

题目:

可以看出每走第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];
	}
}
12345678910111213141516171819

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

如果不明白上图,可以把每条路径都画出来,观察每个数字有多少条路径经过了他,就会一目了然
然后我们就可以自然而然的想到,如果我们每次都把结果保存下来,复杂度就会大大降低

其实答案很简单:
其实这是动态规划很精髓的一部分,是减少复杂度的主要原因
我们都知道,递归一般情况下是可以转化为递推的,不详细解释了,贴上答案:

其实,仔细观察该解题过程,该过程就是标准的动态规划解题过程,如果把该过程画出来(找到每一步的最优解,其他的舍弃)对动态规划会有更深刻的解法
还有就是,递推的另一个好处是可以进行空间优化,如图:

下面总结一下动态规划的解题一般思路:
首先递归应该是我们解决动态规划问题最常用的方法,帅,速度不算太慢
那么递归到动规的一般转化方法为:
如果该递归函数有n个参数,那么就定义一个n维数组,数组下标是递归函数参数的取值范围(也就是数组每一维的大小).数组元素的值就是递归函数的返回值(初始化为一个标志值,表明还未被填充),这样就可以从边界值开始逐步的填充数组,相当于计算递归函数的逆过程(这和前面所说的推导过程应该是相同的).
原文链接:https://blog.csdn.net/ailaojie/article/details/83014821

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

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