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

    1

   3 2

 4 10 1

4 3 2 20

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

输入：三角形的行数n，数字三角形的各个数（从上到下，从左到右）

输出：最大的和。

运行结果：

如果熟悉回溯法，可能会立刻发现这是一个动态的决策问题：每次有两种选择-左下或右下。如果用回溯法求出所有可能的路线，就可以从中选出最优路线。但和往常一样，回溯法的效率太低；一个n层数字三角形的完整路线有条，当n很大时回溯法的速度将让人无法忍受。

为了得到高效的算法，需要用抽象的方法思考问题：把当前的位置（i，j）看成一个状态（还记得么？）然后定义状态（i，j）的指标函数d（i，j）为从格子（i，j）出发时能得到的最大和（包括格子（i，j）本身的值）。在这个状态定义下，原问题的解是d(1,1)

下面看看不同状态之间是如何转移的。从格子（i，j）出发有两种决策。如果往左走，则走到（i+1,j）后需要求“从（i+1，j）”出发后能得到的最大和“这一问题，即d(i+1,j）。类似得，往右走之后需要求解d（i+1，j+1）。由于可以在这两个决策中自由选择，所以应选择d(i+1,j)和d(i+1,j+1)中较大的一个，换句话说，得到了所谓的状态转移方程：

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

如果往左走，那么最好情况等于（i，j）格子里的值a（i，j）与”从（i+1，j）出发的最大总和“之和，此时需注意这里的最大二字。如果连”从(i+1,j)出发走到底部“这部分的和都不是最大的，加上a（i，j）之后肯定也不是最大的。这个性质称为最优子结构，也可以描述成全局最优解包含局部最优解。不管怎样，状态和状态转移方程一起完整的描述了具体的算法。

int a[100][100],n,d[100][100];

第一种方法是递归计算（需注意边界处理）。

int solve1(int i,int j)
{
    /* 递归 (重复计算，效率低) O(2^n)
    把当前位置(i,j)看成一个状态 d[i][j]为从格子出发能得到的最大和 解为d[1][1]
    d(i,j)=a(i,j) +max {d(i+1,j),d(i+1,j+1)} */
    return a[i][j]+(i==n? 0 : max(solve1(i+1,j),solve1(i+1,j+1)));
}

这样做是正确的，但时间效率太低，其原因在于重复计算。在solve(1,1)对应的调用关系树中，solve(3,2)被计算了两次（一次是solve（2,1）需要的，一次是solve（2,2）需要的）。也许读者会认为重复算一两个数没有太大影响，但事实是：这样的重复不是单个结点，而是一颗子树。如果原来的三角形有n层，则调用关系树也会有n层，一共有个结点。

递推计算（需再次注意边界处理）：

int solve2()
{
    /*递推 (逆序枚举) O(n^2)
    i是逆序枚举的，计算d[i][j]前 所需要的d[i+1][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]);
    return d[1][1];
}

程序的时间复杂度显然是，但为什么可以这样计算呢？原因在于：i是逆序枚举的，因此在计算d[i][j]前，它所需要的d[i+1][j]和d[i+1][j+1]一定已经计算出来了。

可以用递推法计算状态转移方程。递推的关键是边界和计算顺序。在多数情况下，递推法的时间复杂度是：状态总数 * 每个状态的决策个数 * 决策时间。如果不同状态的决策个数不同，需具体问题具体分析。

记忆化搜索。程序分成两部分。首先用 memset(d,-1,sizeof(d)); 把d全部初始化为-1，然后编写递归函数。

int solve3(int i,int j)
{
    //记忆化搜索 O(n^2)
     //题目中所说的各个数都是非负的 因此如果计算过某个d[i][j] 则应该非负
    if(d[i][j]>=0) //已经计算过
        return d[i][j];
    return d[i][j]=a[i][j]+(i==n? 0 : max(solve1(i+1,j),solve1(i+1,j+1)));
}

上述程序仍然是递归的，但同时也把计算结果保存在数组d中。题目中所各个数都是非负的，因此如果已经计算过某个d[i][j]，则它应是非负的。这样，只需把所有d初始化为-1，即可通过判断是否d[i][j]>=0得知它是否已经被计算过。

最后，千万不要忘记把计算之后把它保存在d[i][j]中，根据c语言 赋值语句本身有返回值的规定，可以把保存d[i][j]的工作合并到函数的返回语句中。

上述程序的方法称为记忆化，它虽然不像递推法那样显式地指明了计算顺序，然仍然可以保证每个结点只访问一次。

由于i和j都在1-n之间，所有不相同的结点一共只有个。无论以怎样的顺序访问，时间复杂度均为。从是一个巨大的优化，这正是利用了数字三角形具有大量重叠子问题的特点。

一、问题描述

★问题描述：给字一个由n行数字组成的数字三角形（等腰三角形）。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

★算法设计：对于给定的由n行数字组成的数字三角形，计算从三角形的项至底的路径经过的数字和的最大值。

★数据输入：由文件input.txt提供输入数据。文件的第1行是数字三角形的计数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0~99之间。

★结果输出：将计算结果输出到文件output.txt。文件第1行中的数是计算出的最大值。

输入文件示例：input.txt

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出文件示例：output.txt

30

二、问题分析

（1）.输入数据的储存和表示：

先将数字三角形由一个等腰变形为一个直角三角形，便于我们使用矩阵来保存和表示。

矩阵表示如下：

0 0 0 0 0 0

0 7 0 0 0 0

0 3 8 0 0 0

0 8 1 0 0 0

0 2 7 4 4 0

0 4 5 2 6 5

相应输入部分的代码：

for(int i=1;i<=n;i++){

  for(int j=1;j<=i;j++){

  cinfile>>NT[i][j];

  }

  for(int j=i+1;j<=n;j++){

    NT[i][j]=0;

  }

}

（2）.解题思路

基本思路--采用自顶向下的方法

A.思路一：自顶向下依次遍历，在碰到分叉路的时候选择较大的数。（错误--局部最优并不等于整体最优）

比如上述例题按这种方法得到的“最优解”：7+8+1+7+5=27

而实际上的最优解：7+3+8+7+5=30

B.思路二：自顶向下依次遍历，列举出所有路径的大小，最后再进行比较。（正确）

保存数据：首先，我们需要一个矩阵储存当前路径的大小，这里我们使用NT（number triangle）保存原来的数字三角形，使用ST（sum triangle）保存当前路径的大小。由于每个路径数据再往下发展的时候都有两种可能，因此这个矩阵的大小为n*2(n-1)，这里的话我直接使用了2n。

算法设计：

初始化，ST[i][0]=0;ST[0][j]=0;ST[1][1]=NT[1][1]

自顶向下遍历

当前路径的和=上一层路径的和+当前数据；

r[1][1]=a[1][1];

for(int i=2;i<=n;i++){

int count=1;

for(int j=1;j<=i-1;j++){

r[i][count++]=r[i-1][j]+a[i][j];//每一个数据对应两条路径

r[i][count++]=r[i-1][j]+a[i][j+1];

}

}

遍历结束后，ST的数据存储情况

比如10就是路径：7+3的和；

15就是路径：7+8的和；

等等

回溯最优路径：

由于我们在计算最优路径时，用ST保存了所有当前路径的大小。因此我们只需要用最后的最优路径的数值依次往回减就可以求出最优路径了。由于我们的回溯是自底向上，路径的数据顺序是倒着的。因此这里使用了栈来储存路径数据，利用其后进先出的特点回溯出最优路径。

三、详细设计（从算法到程序）

#include<iostream>
#include<stack> 
#include<fstream>
#include<sstream>
using namespace std;
//计算数字三角形最大路径的值
int Numtri(int n,int **a,int **r){
	r[1][1]=a[1][1];
	for(int i=2;i<=n;i++){
		int count=1;
		for(int j=1;j<=i-1;j++){
			r[i][count++]=r[i-1][j]+a[i][j];
			r[i][count++]=r[i-1][j]+a[i][j+1];
		}
	}
}
//回溯最优路径
int Traceback(int n,int posi,int **r,ofstream &outfile){
	stack<int>trace; //建立一个堆栈，利用其后进先出的特点来打印出路径
	int j=posi/2+1,c=r[n][posi];
	for(int i=n-1;i>=0;i--){//从最后一层开始往上回溯
		trace.push(c-r[i][j]);
		c=r[i][j];
		if(j%2==0) j=j/2; 
		else j=j/2+1;
	}
	while(!trace.empty()){
		outfile<<trace.top()<<" ";
		trace.pop();
	}
}

int main(){
	ifstream cinfile;
	cinfile.open("input.txt",ios::in);
	int n;
	cinfile>>n;
	int **NT=new int *[n+1]();
	int **ST=new int *[n+1]();
	for(int i=0;i<=n;i++)
	{
		NT[i]=new int[n+1];
		ST[i]=new int[2*(n+1)];
	}
	for(int i=0;i<=n;i++){
		NT[0][i]=0;
		NT[i][0]=0;
	}
	for(int i=1;i<=n;i++){
	  for(int j=1;j<=i;j++){
	  	cinfile>>NT[i][j];
	  }
	  for(int j=i+1;j<=n;j++){
	    NT[i][j]=0;
	  }
    }
    for(int i=0;i<=n;i++)
       for(int j=0;j<=2*n;j++) ST[i][j]=0;    
    cinfile.close();
    
    ofstream outfile;
    outfile.open("output.txt",ios::out);
    Numtri(n,NT,ST);
	int Max=ST[n][1],pos=1;
	for(int i=2;i<=2*n;i++){
		if(Max<ST[n][i]){
			Max=ST[n][i];
			pos=i;
		}
	}
	outfile<<Max<<endl;
	Traceback(n,pos,ST,outfile);
	return 0;
}
/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/	

四、程序运行结果

五、分析与总结

在做动态规划这一类问题时一定要注意很多时候局部最优解并不等于整体最优解。

美图：

问题描述：
　　　　　　　　　７
　　　　　　　　３　８
　　　　　　　８　１　０
　　　　　　２　７　４　４
　　　　　４　５　２　６　５　
　　
　　给定一个数字三角形，如上，在这个三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。求出这个最大和。

一. 我们先考虑使用递归来解决。

用二维数组Ｄ来存放数字三角形，问题转换如下：

D(i，j)：表示第 i 行第 j 列的数字。（i，j从0开始）
Sum(i，j)：表示从 D(i，j) 到底边的最优解，即：从 D(i，j) 到底边的各条路径中，数字之和最大的一个。
问题：求 Sum(0,0)。即：第0行第0列到底边的路径的最大和。

1. 当只有一行时，它的最大路径和就是它本身。
   即：Sum(i,j) =D(i,j)
2. 其次，它的最大路径和就是它本身加上它下面左右两个元素的最大路径和的较大者。因为是使用二维数组来存数字，就是它本身加上他正下方和他右下方两个元素的最大路径和的较大者。
   即：Sum(i,j) =max{Sum(i+1,j)，Sum(i+1，j+1)}+D(i，j)

写出递归方程：

S u m ( i , j ) = { D ( i , j ) ， i==N-1(底行) m a x { S u m ( i + 1 , j ) ， S u m ( i + 1 ， j + 1 ) } + D ( i ， j ) , 0<i，j<N Sum(i,j) = \begin{cases} D(i,j)， & \text{i==N-1(底行)} \\ max\{Sum(i+1,j)，Sum(i+1，j+1)\}+D(i，j), & \text{0<i，j<N} \end{cases} Sum(i,j)={D(i,j)，max{Sum(i+1,j)，Sum(i+1，j+1)}+D(i，j),​i==N-1(底行)0<i，j<N​

根据递归方程写出递归函数。

#include<iostream>
using namespace std;
const int N = 100;
int D[N][N];
int max(int a, int b)
{
	int m = a > b ? a : b;
	return m;
}
int fun_d(int i,int j,int n)
{
	if (i == n-1)
		return D[i][j];
	int Sum_L = fun_d(i + 1, j, n);
	int Sum_R = fun_d(i + 1, j + 1, n);
	return max(Sum_L, Sum_R)+D[i][j];

}
int main()
{
	int n, i, j;

	cin >> n;//n行数
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			cin >> D[i][j];
		}
	}
	int MaxSum = fun_d(0,0,n);
	cout << MaxSum << endl;
	return 0;
}

然而并没有，一般情况下，递归的时间复杂度都比较高，我们来看一下这个递归的时间复杂度。

嗯？花里胡哨的什么东西？
　　
　　这个表中红色的数字就是递归过程中每个元素要进行的计算次数，what？没错，就是存在大量的重复计算，这就导致了算法的时间复杂度非常高。将每行红色的数字加起来，就是这个算法的时间复杂度，即：$O(2^n)$。what？指数级别的时间复杂度，那肯定爆炸。所以，我又默默打开了电脑，打算用头发换思路。

改进：
　　如果每算出一个元素的最优解，就把它保存起来，下次需要的时候直接调用即可，就可避免重复多次的计算。我们创建一个二维数组 Sum[M][N] 来保存最优解。那这样的时间复杂度是多少呢？一共需要计算多少个数据，时间复杂度就是多少，假设有 n 行数字，那么数字总数就是 n(n+1)/2，即：时间复杂度是 $O(n^2)$。

二. 通讯录式的递归方式。

也称为记忆型的递归程序。
　　我们牺牲空间和头发换时间，用一个二维数字 Sum[M][N] 来存放每一个元素到底边的最大和。初始时，给他每个元素都初始为 -1 ，表示该元素还没有计算出来过最优解。
　　在递归的时候，如果 Sum[i][j] != -1，就表示该元素已经计算出来过最优解，我们可以直接调用它。然后当它递归到最后一行元素时，它的最优解就是当前的元素值。否则就在它正下方和右下方的元素的最优解中取一个较大者再加上该值发放该位置。

C++实现：

#include<iostream>
using namespace std;
const int N = 100;
int D[N][N];
int Sum[N][N];//存放每一个数字到底边的最大和
int max(int a, int b)
{
	int m = a > b ? a : b;
	return m;
}
int fun_f(int i, int j, int n)
{
	if (Sum[i][j] != -1)
		return Sum[i][j];
	if (i == n - 1)
		Sum[i][j] = D[i][j];
	else 
	{
		int Sum_L = fun_f(i + 1, j, n);//下方
		int Sum_R = fun_f(i + 1, j + 1, n);//右下方
		Sum[i][j] = max(Sum_L, Sum_R) + D[i][j];
	}
	return Sum[i][j];

}
int main()
{
	int n, i, j;

	cin >> n;//n行数
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			cin >> D[i][j];
			Sum[i][j] = -1;//表示该元素还没有计算出来最优解
		}
	}
	int MaxSum = fun_f(0, 0, n);
	cout << MaxSum << endl;
	return 0;
}

Java实现：

package abcd;

import java.util.Scanner;

public class Example2_1{
    public static void main (String args[]){
        Scanner in = new Scanner(System.in);
        int[][] D = new int[100][100];
        int[][] Sum =new int[100][100];
        int n,i,j;
        n= in.nextInt();
        for (i = 0; i < n; i++)
        {
            for (j = 0; j <= i; j++)
            {
                D[i][j]=in.nextInt();
                Sum[i][j] = -1;//表示该元素还没有计算出来最优解
            }
        }
        int MaxSum = fun_f(D,Sum,0, 0, n);
        System.out.println(MaxSum);

    }
    public static int fun_f(int[][] D,int[][] Sum,int i,int j,int n)
    {
        if (Sum[i][j] != -1)
        {
            return Sum[i][j];
        }
        if (i == n - 1)
        {
            Sum[i][j] = D[i][j];
        }
        else
        {
            int Sum_L = fun_f(D,Sum,i + 1, j, n);//下方
            int Sum_R = fun_f(D,Sum,i + 1, j + 1, n);//右下方
            Sum[i][j] = max(Sum_L, Sum_R) + D[i][j];
        }
        return Sum[i][j];
    }
    public static int max(int a, int b)
    {
        int m = a > b ? a : b;
        return m;
    }
}

这个图就是最终每个元素到底部的最大路径和。

它的最后一行就是本来的元素，嗯？是不是可以不用递归，用我们的 由已知推未知大法 是不是可以解决呢？

三. 由已知推未知大法

算法思想：
　　由上面可以看出，存最优解的二维数组的最后一行就是原来数组的最后一行的值，而且一个元素都是可以由该元素的正下方元素和右下方元素推出来，刚好可以根据最后一层元素，层层递推，直到推迟第0行第0列的元素。
　　首先，给Sum数组的最后一行初始化为原本数组的最后一行，即：Sum[n - 1][i] = D[n - 1][i];。
　　然后，使用双层循环来递推每一个元素。即：Sum[i][j] = max(Sum[i + 1][j], Sum[i + 1][j + 1]) + D[i][j];

#include<iostream>
using namespace std;
const int N = 100;
int D[N][N];
int Sum[N][N];//存放每一个数字到底边的最大和
int max(int a, int b)
{
	int m = a > b ? a : b;
	return m;
}
int fun_f_2(int n)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		Sum[n - 1][i] = D[n - 1][i];
	}
	for (i = n - 2; i >= 0; i--)
	{
		for (j = 0; j <= i; j++)
		{
			Sum[i][j] = max(Sum[i + 1][j], Sum[i + 1][j + 1]) + D[i][j];
		}
	}
	return Sum[0][0];
}
int main()
{
	int n, i, j;

	cin >> n;//n行数
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			cin >> D[i][j];
		}
	}
	int MaxSum = fun_f_2(n);
	cout << MaxSum << endl;
	return 0;
}

呃呃呃，这样的话，算法的时间复杂度同样是$O(n^2)$，我们写它还有什么意义，莫慌、莫慌，且往下看。
　　
　　这个算法中，我们使用了二维数组来记录已求出的结果，然后进行层层递推，得到最终的结果。但是，我们可以看到，这个二维数组的每一行在完成它的递推任务之后，它就没用了，so，我们是不是可以用一个一维数组来代替这个二维数组呢？

四. 压缩空间

这个图中，比如说要计算 D[3][0] 元素的最优解，就是 4 和 5 的较大者加上 D[3][0] ，算完之后，这个 4 就没用了，我们可以直接将 D[3][0] 元素的最优解 7 直接存放在 4 的位置上，循环往复。只需要一个一维数组就够了，最终，这个一位数组的首元素，就是最终的结果。

#include<iostream>
using namespace std;
const int N = 100;
int D[N][N];
int max(int a, int b)
{
	int m = a > b ? a : b;
	return m;
}
int Sum_1[N];
int fun3(int n)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		Sum_1[i] = D[n - 1][i];
	}
	for (i = n - 2; i >= 0; i--)
	{
		for (j = 0; j <= i; j++)
		{
			Sum_1[j] = max(Sum_1[j] , Sum_1[j + 1])+D[i][j];
		}
	}
	return Sum_1[0];
}
int main()
{
	int n, i, j;

	cin >> n;//n行数
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			cin >> D[i][j];
		}
	}
	int MaxSum = fun3(n);
	cout << MaxSum << endl;
	return 0;
}

嗯？一维数组？那个存原始数据的不就是的二维数组吗，二维数组不就是多个一维数组构成的嘛，有个大胆的想法，嘿嘿嘿，是不是这个一维数组也可以不要，用存原始数据的二维数组的最后一行来代替这个一维数组。

五. 极限压缩

C++ 实现：

#include<iostream>
using namespace std;
const int N = 100;
int D[N][N];
int max(int a, int b)
{
	int m = a > b ? a : b;
	return m;
}
int fun3(int n)
{
	int i, j;
	for (i = n - 2; i >= 0; i--)
	{
		for (j = 0; j <= i; j++)
		{
			D[n-1][j] = max(D[n-1][j] , D[n-1][j + 1])+D[i][j];
		}
	}
	return D[n-1][0];
}
int main()
{
	int n, i, j;

	cin >> n;//n行数
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			cin >> D[i][j];
		}
	}
	int MaxSum = fun3(n);
	cout << MaxSum << endl;
	return 0;
}

Java实现：

package abcd;
import java.util.Scanner;
public class Example2_1{
    public static void main (String args[]){
        Scanner in = new Scanner(System.in);
        int[][] D = new int[100][100];
        int n,i,j;
        n= in.nextInt();
        for (i = 0; i < n; i++)
        {
            for (j = 0; j <= i; j++)
            {
                D[i][j]=in.nextInt();
            }
        }
        int MaxSum = fun3(D,n);
        System.out.println(MaxSum);

    }
    public static int fun3(int[][] D,int n)
    {
        int i, j;
        for (i = n - 2; i >= 0; i--)
        {
            for (j = 0; j <= i; j++)
            {
                D[n-1][j] = max(D[n-1][j] , D[n-1][j + 1])+D[i][j];
            }
        }
        return D[n-1][0];
    }

    public static int max(int a, int b)
    {
        int m = a > b ? a : b;
        return m;
    }
}

编程之美，真的让人着迷。这就是许多编程大师以“聪明绝顶”为代价也要追求的东西。