动态规划初步 数字三角形（算法竞赛入门经典读书笔记）

问题简述：

如图示数字三角形。从第一行的数开始，每次可以往左下或右下走一步，直到走到最下行，把沿途经过的数全部加起来，如何走才能使得这个和尽量大？

状态定义：

把每个数字的 当前位置(i,j) 表示如下：

这里定义几个状态：（务必理解这两个状态）

a[ i ][ j ]： 存储对应位置的数值。如a[1][1]=1，a[2][1]=3。

d[ i ][ j ]： 从（i，j）出发时能得到的最大和(包括其本身的值)。如d[3][1]=8。即 d(i,j) = a(i,j) + max { d(i+1, j) , d(i+1, j+1) }

解决方法：

1. 递归计算：不推荐，由于相同的子问题被重复计算了多次，故效率低下
2. 递推计算：推荐使用，关键是边界和计算顺序
3. 记忆化搜索：推荐使用，不必确定计算顺序，但要记录每个状态“是否已经计算过”

1.递归计算：

由上述得出的方程 d(i,j) = a(i,j) + max { d(i+1, j) , d(i+1, j+1) } （这个方程就是状态转移方程）

可知题目要求的就是d(1,1)，而d(1,1)是d(2,1)和d(2,2)中的较大值加上a(1,1）。

即：

d(1,1)=a(1,1)+max{ d(2,1) , d(2,2) }

d(2,1)=a(2,1)+max{ d(3,1) , d(3,2) }

d(2,2)=a(2,2)+max{ d(3,2) , d(3,3) }

… …

显然，这就是个递归，如果我们按照这个思路写完代码就完美的实现了方法一递归计算

递归计算代码：

int solve(int i,int j){
	return a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));
	//如果是最后一行返回0，否则按方程计算 
} 
           

但是，上面三个式子中加粗的部分 d(3,2) 被重复计算了两遍，我会觉得重复一两个数没有太大影响。

可事实是：这样的重复不是单个结点，而是一棵子树

假设继续计算刚刚的d(2,1)：

d(2,1)=a(2,1)+max{ d(3,1) , d(3,2) }

d(3,1)=a(3,1)+max{ d(4,1) , d(4,2) }

d(3,2)=a(3,2)+max{ d(4,2) , d(4,3) }

这个三角形还只有四层，如果三角形是n层，则调用关系树也会有n层，一共有2n -1结点。

就一直重复计算吖重复计算重复计算~怎么不要让它重复计算呢？如下

2.记忆化搜索：

记忆化看着好高级哦 其实就是当计算过一次d(i,j)后，就将计算结果存储好并记住这个值我是算过了的，即记录每个状态“是否已经计算过”,下次使用时判断如果这个d(i,j)已经计算过了呢就直接调用，没有计算过我再计算。这样一来，就解决了重复计算的问题

具体操作如下：

1. 用“ memset(d,-1,sizeof(d)) ”把d全部初始化为-1
2. 计算结果保存在d[ i ][ j ]中。即如果已经计算过某个d[ i ][ j ]，它应该是非负的
3. 通过判断是否d[ i ][ j ]>=0得知它是否被计算过

记忆化搜索代码：

int solve(int i,int j){
	if(d[i][j]>=0)return d[i][j];//若已经计算过直接返回值 
	return d[i][j]=a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));
	//如果是最后一行返回0，否则按方程计算 
} 
           

3.递推计算：

其关键在于逆序，从倒数第二行开始，将每个数与其左右两个底数中的较大值相加，同理再倒数第三行第四行…最后最顶层的值就是总和最大值。

因此保证了在计算d[i][j]之前，所需的d[i+1][j+1]一定已经计算出来了，过程如下图所示：

递推计算代码：

int i,j;
for(j=1;j<=n;j++)d[n][j]=a[n][j];//边界处理
for(i=n-1;i>=1;i--)//倒数第二行开始
	for(j=1;j<=i;j++)
		d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]); 
           

之前蓝桥杯算法训练写过一个数字三角形答案，现在看来当时用的递推hhh

https://blog.csdn.net/weixin_42324771/article/details/87023413