动态规划是解决大多数复杂问题的一种解题思路，其操作步骤和递归算法类似，都是先从问题本身抽象出规律，并整理出计算公式，然后从公式出发，使用递归算法、递推或者记忆搜索法等算法进行求解。

万恶的数塔问题

1.问题描述

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

现从首行走到末行，每次只能往下或者往右走一格，求如何行走使得各位上数字之和最大

2.分析

假定f(i,j)表示第i行第j列位置的最大值，则欲求f(1,1)，则必须知道f(2,1)和f(2,2)中最大值，然后取其中最大值加上7，则是f(1,1)。于是有了：

3.代码

根据2中的分析，得到了公式，根据公式可以写递归、递推和技术搜索法三种算法：

1.递归算法

int f(int i, int j){
  if(i == N){
    return A[i][j];
  }else{
    return A[i][j] + Math.max(f(i+1,j),f(i+1,j+1));
  }
}

2.记忆搜索法

int MEM[N][M];
int f(int i, int j){
  if(i == N){
    return A[i][j];
  }else if(MEM[i][j] != 0){
    return MEM[i][j];
  }else{
    MEM[i][j] = A[i][j] + Math.max(f(i+1,j),f(i+1,j+1));
    return MEM[i][j];
  }
}

3.递推

int MEM[N][M];
int f(){
  for(int i=0;i<N;i++){
    MEM[N-1][i] = A[N-1][i];
  }
  for(int i=N-2;i>=0;i--){
    for(int j=0;j<=i;j++){
      MEM[i][j] = Math.max(MEM[i+1][j], MEM[i+1][j+1]); 
    }
  }
  return MEM[0][0];
}

ATTENTION: 由递归转为递推，可以使用列表法实现，先将已知条件列举出来，然后根据递归公式，一步步求解未知条件【注意边界条件的考虑】