动态规划

将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。

数字三角形问题：

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

问题描述：

输入数据

输入的第一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N 行给出数字三角形。数字三角形上的数的范围都在0 和100 之间。

输出要求

输出最大的和。

输入样例

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出样例

思路：

一、递归

这道题目可以用递归的方法解决。基本思路是：

以D( r, j)表示第r 行第 j 个数字(r，j 都从1 开始算)，以MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的最佳路径的数字之和，则本题是要求 MaxSum(1, 1) 。

从某个D(r, j)出发，显然下一步只能走D(r+1, j)或者D(r+1, j+1)。如果走D(r+1, j)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j) + D(r, j)；如果走D(r+1, j+1)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j+1) + D(r, j)。所以，选择往哪里走，就看MaxSum(r+1, j)和MaxSum(r+1, j+1)哪个更大了。

但是效率太低，N=100的时候，已经算不动了。

二、动态规划

在上面的例子里，有递推公式：

因此，不需要写递归函数，从aMaxSum[N-1]这一行元素开始向上逐行递推，就能求得aMaxSum[1][1]的值了。

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 vector< vector<int> > num;
 5 vector< vector<int> > num_temp;
 6 vector<int> allnumbers;
 7 
 8 int maxsum(int i,int j)
 9 {
10     if(i+1==num.size())
11         return num[i][j];
12     if(num_temp[i+1][j]==-1)
13         num_temp[i+1][j]=maxsum(i+1,j);
14     if(num_temp[i+1][j+1]==-1)
15         num_temp[i+1][j+1]=maxsum(i+1,j+1);
16     if(num_temp[i+1][j]>=num_temp[i+1][j+1])
17         return num_temp[i+1][j]+num[i][j];
18     else
19         return num_temp[i+1][j+1]+num[i][j];
20 }
21 int main()
22 {
23     int N;
24     cin>>N;
25     for(int i=0;i<N;i++)
26     {
27         vector<int> t1,t2;
28         for(int j=0;j<i+1;j++)
29         {
30             t1.push_back(i+j+i*j);
31             t2.push_back(-1);
32         }
33         num.push_back(t1);
34         num_temp.push_back(t2);
35     }
36     //计算最大路径的和
37     cout<<maxsum(0,0)<<endl;
38     //计算最大路径上的每一个数字
39     int m1,m2=0;
40     int result=maxsum(0,0);
41     for(m1=0;m1<num_temp.size()-1;m1++)
42     {
43         if(num_temp[m1+1][m2]>=num_temp[m1+1][m2+1])
44         {allnumbers.push_back(result-num_temp[m1+1][m2]);result=num_temp[m1+1][m2];m2=m2;}
45         else
46             {allnumbers.push_back(result-num_temp[m1+1][m2+1]);result=num_temp[m1+1][m2+1];m2=m2+1;}
47     }
48     allnumbers.push_back(num_temp[m1][m2]);
49     for(vector<int>::iterator iter=allnumbers.begin();iter!=allnumbers.end();iter++)
50         cout<<*iter<<endl;
51     system("pause");
52     return 0;
53 }

注：代码中附带了记录最大路径上的每一个数字的方法。