9.1 数字三角形_数字三角形回溯法

9.1 数字三角形

这章我们开始介绍一些有关动态规划的知识和问题。动态规划严格意义上说并不是一种特定的算法，而是一种处理问题的思想和手段。

9.1.1 问题描述与状态定义

数字三角形问题：有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外的每个数的左下方和右下方各有一个数。

从第一行的数开始，每次可以往左下或者右下走一格，直到走到最下行，把沿途经过的所有数全部加起来，如何走才能使得这个和最大。

分析：这个问题可以用回溯法解决，但是如果用回溯法求出所有可能的路线的话，一个n层数字三角形的完整路线有2^n-1条，时间复杂度是指数递增的。所以书上提供了另一种思路。

将位置(i,j)看作一个状态(i表示第几层，j表示该层从左往右的第几个)，d(i,j)表示从位置(i,j)出发能够得到的最大值(包括位置(i,j)本身的值)。我们知道可以从(i,j)的位置往左下或者右下，我们假设d(i+1,j)和d(i+1,j+1)选择的路径分别为s1和s2。我们知道从(i,j)向下只有可能到(i+1,j)和(i+1,j+1)这两个位置，当到了这两个位置后，我们需要选择向下最优的路径才能够得到最大的和。于是从(i,j)出发向左下或右下分别得到的最优路径的值分别是a(i,j)+d(i+1,j)和a(i,j)+d(i+1,j+1)，得到：

d(i,j)=a(i,j)+max(d(i+1,j),d(i+1,j+1))

我们称上面的公式为状态转移方程。

动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。若给定了第k阶段的状态Sk以及决策Uk,则第k+1阶段的状态S(k+1)也就完全确定。也就是说S(k+1)与Sk,Uk之间存在一种明确的数量对应关系,记为Tk(Sk,Uk),即有S(k+1)= Tk(Sk,Uk)。 这种用函数表示前后阶段关系的方程,称为状态转移方程。

9.1.2 记忆化搜索与递推

有了状态转移方程，接下来的任务就是编写计算过程。

方法一：递归计算，代码如下：

int solve(int i,int j){
	return a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));
}
1
2
3

这个代码没什么好分析的，条件运算符确定边界，其余的就是翻译上面的公式，但没有体现状态转移方程的优势。

这么做会重复计算很多状态的值，于是进行优化。

方法二：递推计算，代码如下：

int i,j;//先把最下面一层状态的d值全部预备好
for (int 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]);
1
2
3

上面一个方法是从上到下计算的，而这里的方法是从下到上计算的。由于我们这里可以确定第i层的d值都是由第i+1层的d值得到的，也就是说将最底层的值全部计算出来可以很自然地向上一层一层推理，这是一个很自然的想法。

方法三：记忆化搜索。首先将d值全部赋值为-1，然后编写递归函数：

memset(d,-1,sizeof(d));
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)));
}
1
2
3
4
5

这个方法和方法一有什么区别呢？它将计算结果全部保存在d数组中，题目中说每个位置的数都是非负的，也就是说已经计算出的d值一定是非负的，我们可以通过这种方式将已经计算过的d值直接return，避免重复计算。

事实上这个方法我们早在前面章节的习题中就介绍过了hhhh