相关题目链接：
CODE-VS 1220 数字三角形
1.数字三角形
第一题和第二题一样，数字三角形问题，此处写三种不同的代码，但是总的动态规划思想是一致的。
引言
如果熟悉回溯法，可能会发现这是一个动态的决策问题：每次有两种选择：向下（左下）走或向右下走，如果用回溯法求出所有路线，就可以从中选出最优路线。但是效率太低，n层的数组三角形的完整路线有2^n-1条，当n很大时回溯法很慢。
为了得到高效的算法，需要抽象的思考（动态规划思想），把当前的位置（i，j）看成一种状态，然后定义状态（i，j）的指标函数sovle（i，j）为从（i,
j）出发时能得到的最大和，在这个状态定义下，原问题转化为求sovle（1，1）。得到所谓的 状态转移方程:
dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]); 如果向下（左下）走，那么最好的情况等于a[i][j]+从(i+1, j)出发的最大和，此时需注意”最大“二字，如果连从(i+1,
j)出发到达底部的这部分和都不是最大的，那么加上a[i][j]之后也不是最大的。这个性质称为最优子结构，也可以描述为”全局最优解包含局部最优解“。状态和状态转移方程（最优决策）一起完整的描述了具体的算法。
方法一：搜索法
/*************
> File Name: 1002.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2015年12月08日 星期二 13时03分07秒
***************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[1000][1000];
int n;
int s = 0;
int d[1000][1000];
int sovle_test(int i , int j)
{//（回溯）这样做是正确的，但是时间效率太低，其原因在于重复计算，只是提供思路
if(i==n) return a[i][j];
return a[i][j] + sovle_test(sovle_test(i+1, j), sovle_test(i+1, j+1));
}
int sovle(int i, int j)
{//用数组d记录已经计算过得点到最低端的最大值，这种方法称为“记忆化搜索”（深搜+记忆化）
if(d[i][j] >= 0) return d[i][j];
return d[i][j] = a[i][j] + (i == n? 0: (sovle(i+1, j) > sovle(i+1, j+1)? sovle(1+i, j):sovle(i+1, j+1)));
}
int main()
{
memset(d, -1, sizeof(d));
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= i; j++)
scanf("%d", &a[i][j]);
}
printf("%d", sovle(0, 0));
}方法二：递推计算
#include<stdio.h>
#include<iostream>
using namespace std;
const int N = 508;
int dp[N][N];
int a[N][N];
int main()
{
int n;
cin>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
for(int i = n; i >= 1; i--)//从底部开始，想一下可不可以上面头开始？为什么？
for(int j = 1; j <= i; j++)
dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
cout<<dp[1][1]<<endl;
}
从头向下当然是可以的，只不过dp数组的含义发生变化了，上面代码dp[i][j] 表示从（i,j）开始到底层能得到的最大和。
如果从头向下，如下面代码，dp[i][j]表示从(i, j)到(1, 1)的最大和，也能求得结果。
/*************
> File Name: 1220_数字三角形.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年03月09日 星期三 22时33分00秒
***************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1009;
int dp[N][N];
int a[N][N];
int main()
{
int n;
cin>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
{
scanf("%d", &a[i][j]);
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
dp[i][j] = a[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
}
}
//找到从（1， 1）开始到达底层的哪一个点能取得最大和
for(int i = 1; i <= n; i++)
ans = max(ans, dp[n][i]);
printf("%d\n", ans);
return 0;
}2.矩阵取数问题
题目描述
一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。
例如：3 * 3的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为：11。
这个题目个上面的数字三角形类似，很容易的到状态转移方程：
如果dp[i][j]表示从(i, j)点到右下角的点，所能获得的最大价值，则
dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i][j+1]; ans = dp[1][1];
如果dp[i][j]表示从(i, j)点到左上角的点，所能获得的最大价值，则
dp[i][j] = a[i][j]+ max(dp[i-1][j], dp[i][j-1]);
一定要注意其中的差别，以及循环的起止，和边缘的判断。
下面附代码：
/************
> File Name: 1083.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年03月03日 星期四 17时15分33秒
*********************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 508;
int a[N][N] = {0};
int dp[N][N] = {0};
int main()
{
int n;
cin>>n;
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
for(int i = n+1; i--; )
for(int j = n+1; j--;)
{
dp[i][j] = max(dp[i][j+1], dp[i+1][j]) + a[i][j];
}
/*
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = a[i][j]+max(dp[i-1][j],dp[i][j-1];
*/
cout<<dp[1][1];
//cout<<dp[n][n];
return 0;
}3.打印路径
打印的时候可以根据结果反推，以数字三角形为例：
如果dp[i][j] = a[i][j] + dp[i+1][j]则其向（左）下走
否则向右下走，
void print(int i, int j)
{
if(i > n) return;
printf("%d\n", a[i][j]);
if(dp[i][j] == dp[i+1][j])
print(i+1, j);
else
print(i+1, j+1);
}矩阵问题的路径与三角形相似，这里就不放代码了。