例9.2数字金字塔
观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。
每一步可以从当前点走到左下方的点也可以到右下方的点
方法一:
从最高点按照规则走到最低点的路径的最大的权值和，路径起点终点固定，走法规则明确，可以考虑用搜索算法
定义递归函数 void Dfs（int x,int y, int Curr），其中x,y表示当前已从（1,1）走到（x,y),目前已走路径上的权值和为Cur
当x=N时，到达递归出口，如果Cur比Ans大，则把Ans更新为Cur；
否则向下一行两个位置行走，即递归执行Ds（x+1，y,Cur+A[x+1][y]）和Dfs（x+1，y+1，Cur+A[x+1][y+1]）
#include <iostream>
#include<bits/stdc++.h>
using namespace std;const int MAXN=1005;
int A[MAXN][MAXN],F[MAXN][MAXN],N,Ans;//递归函数
void Dfs(int x,int y,int Cur){//递归的结束条件//查询到最后一行if(x==N){//如果当前路径和大于之前的if(Cur>Ans){Ans=Cur;}return ;}//向下一行两个位置行走Dfs(x+1,y,Cur+A[x+1][y]);Dfs(x+1,y+1,Cur+A[x+1][y+1]);
}//主函数
int main(){//数据初始化//输入行数和数字cin>>N;for (int i = 1; i <=N ; ++i) {for (int j = 1; j <=i ; ++j) {cin>>A[i][j];}}//初始化长度Ans=0;//调用递归函数Dfs(1,1,A[1][1]);//打印输出答案cout<<Ans<<endl;return 0;
}方法二：
方法一之所以会超时，是因为进行了重复搜索
记忆化搜索需要对方法一中的搜索进行改装。由于需要记录从一个点开始到终点的路径的最大权值和，因此我们重新定义递归函数Dfs
①第一步向左：那么从（x,y）出发到终点的这类路径就被分成两个部分，先从（x,y）到（x+1，y）再从（x+1，y）到终点，第一部分固定权值就是A[x][y]，要使得这种情况的路径权值和最大，那么第二部分从（x+1，y）到终点的路径的权值和也要最大，这一部分与前面的Dfs（x,y）的定义十分相似，仅仅是参数不同，因此这一部分可以表示成Dfs（x+1，y）。综上，第一步向左的路径的最大权值和为A[x][y]+Dfs(x+1,y)
②第一步向右：这类路径要求先从（x,y）到（x+1，y+1）再从（x+1.y+1）到终点，分析方法与上面一样，这类路径最大权值和为A[x][y]+Dfs（x+1，y+1）；为了避免重复搜索，我们开设全局数组F[x][y]记录从（x,y）出发到终点路径的最大权值和，一开始全部初始化为-1表示未被计算过。在计算Dfs（x,y）时，首先查询F[x][y]，如果F[x][y]不等于-1，说明Ds（x,y）之前已经被计算过，直接返回F[x][y]即可，否则计算出Dfs（x,y）的值并存储在F[x][y]中。
#include<iostream>
#include <cstring>using namespace std;
const int MAXN=505;
int A[MAXN][MAXN],F[MAXN][MAXN],N;//递归函数
int Dfs(int x,int y){//先判断是否可行if(F[x][y]==-1){if(x==N){F[x][y]=A[x][y];}else{F[x][y]=A[x][y]+max(Dfs(x+1,y),Dfs(x+1,y+1));}}return F[x][y];
}//主函数
int main(){//数据初始化cin>>N;for (int i = 1; i <=N ; ++i) {for (int j = 1; j <=i ; ++j) {cin>>A[i][j];}}memset(F,-1, sizeof(F));//调用函数Dfs(1,1);//输出数据cout<<F[1][1]<<endl;return 0;
}方法三：
动态规划（顺推法）：
上面方法二的记忆搜索本质上已经是动态规划了
①确定状态：
题目要求从（1,1）出发到最底层路径最大权值和，路径中是各个点串联而成，路径起点固定，终点和中间点相对不固定。因此定义F[x][y]表示从（1,1）出发到达（x,y）的路径最大权值和。最终答案Ans=max{F[N][1]，F[N][2]，...F[N][N]}
②确定状态转移方程和边界条件：
不去考虑（1,1）到（x,y）的每一步是如何走的考虑最后一步是如何，根据最后一步是向左还是向右分成以下两种情况：
向左：最后一步是从（x-1，y）走到（x,y），此类路径被分割成两部分，第一部分是从（1,1）走到（x-1，y），第二部分是从（x-1，y）走到（x,y），要计算此类路径的最大权值和，必须用到第一部分的最大权值和，此部分问题的性质与F【x】【y】的定义一样，就是F【x-1， y】，第二部分就是 A【x】【Y】，两部分相加即得到此类路径的最大权值和为F【x-1，y】+A【x】【y】；
向右：最后一步是从（x-1，y-1）走到（x,y），此类路径被分割成两部分，第一部分是从（1,1）走到（x-1，y），第二部分是从（x-1，y）走到（x,y），分析方法如上。此类路径的最大权值和为F【x-1，y-1】+A【x,y】； F【x】【y】的计算需要求出上面两种情况的最大值。综上，得到状态转移方程如下：
F【x】【y】=max{ F【x-1，y-1】，F【x-1】【y】}+A【x,y】
与递归关系式还需要递归终止条件一样，这里我们需要对边界进行处理，以防无限递归下去。观察发现计算F【x】【y】时需要用到F【x-1】【y-1】和F【x-1，y】，是上一行的元素，随着递归的深入，最终都要用到第一行的元素F【1】【1】，F【1】【1】的计算不能再使用状态转移方程来求，而是应该直接赋予一个特值A【1】【1】。这就是边界条件。
③程序实现：
由于状态转移方程就是递归关系式，边界条件就是递归终止条件，所以可以用递归来完成，递归存在重复调用，利用记忆化可以解决重复调用的问题，方法二已经讲过。记忆化实现比较简单，而且不会计算无用状态，但递归也会受到“栈的大小”和“递推十回归执行方式”的约束，另外记忆化实现调用状态的顺序是按照实际需求而展开，没有大局规划，不利于进一步优化。
这里使用一种迭代的方法
#include<iostream>
#include<algorithm>
using namespace std;const int MAXN=1005;
int A[MAXN][MAXN],F[MAXN][MAXN],N;int main(){//初始化数据cin>>N;for (int i = 1; i <=N ; ++i) {for (int j = 1; j <=i ; ++j) {cin>>A[i][j];}}F[1][1]=A[1][1];//使用迭代法处理for (int i = 2; i <=N ; ++i) {for (int j = 1; j <=i ; ++j) {//所在点的值=上一步max{右半部,左半部}+上一步到这一步的值F[i][j]=max(F[i-1][j-1],F[i-1][j])+A[i][j];}}int ans=0;for (int i = 1; i <=N ; ++i) {ans=max(ans,F[N][i]);}//输出结果cout<<ans<<endl;return 0;
}//方法四：
//动态规划（逆推法）：
//此题如果用贪心算法得不到最优解（因为贪心算法要求每一步得到的数最大，但是最后的和不是最大，贪心的问题：目光短浅）
//动态规划求解：过程归纳为：自顶向下分析，自底向上计算
//基本方法：
//划分阶段：按三角形的行划分阶段，若有n行，则有n-1个阶段。
//A.从根结点13出发，选取它的两个方向中的一条支路，当到倒数第二层时，每个结点其继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。
//B.自底向上计算：（给出递推式和终止条件）
//①从底层开始，本身数即为最大数；
//②倒数第二层的计算，取决于底层的数据。以此类推
//C.使用直角三角形便于搜索，使用三维数组表示数塔
#include <iostream>
#include <cstring>
using namespace std;//主函数
int main(){//数据初始化int n,x,y;int a[51][51][4];//输入行数cin>>n;//输入数据memset(a,0, sizeof(a));for (x = 1; x<=n ; ++x) {for (y= 1; y<=x ; ++y) {cin>>a[x][y][1];a[x][y][2]=a[x][y][1];a[x][y][3]=0;}}for (int x = n-1; x>=1 ; x--) {for (int y = 1; y <=x ; ++y) {//选择路径，保留最大路径值if(a[x+1][y][2]>a[x+1][y+1][2]){a[x][y][2]=a[x][y][2]+a[x+1][y][2];a[x][y][3]=0;}else{a[x][y][2]=a[x][y][2]+a[x+1][y+1][2];a[x][y][3]=1;}}}cout<<a[1][1][2]<<endl;y=1;//输出数塔值的路径for (int x = 1; x <=n-1 ; ++x) {cout<<a[x][y][1]<<"->";y=y+a[x][y][3];}cout<<a[n][y][1]<<endl;return 0;
}