数字塔问题(递归，递推和记忆化搜索到动态规划)

来自刘汝佳的《算法竞赛入门经典（第二版）》，下面实现代码均为Java

动态规划初步

数字三角形问题（数字塔）：有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外的每个数的左下方和右下方各有一个数。如下图所示：计算从顶至底的路径，使得总和最大。

解题思路：
定义状态d(i, j)为从(i, j)出发时能得到的最大和，从(i, j)出发有两种决策，往左或者往右。
要求从(i, j)出发走到底部的最大值d(i, j)，则相当于选择从左下走或者从右下走中的较大值，即d(i+1, j)和d(i+1, j+1)的较大值，然后加上a(i, j)，可得状态转移方程 d(i, j) = a(i, j) + max(d(i+1, j), d(i+1, j+1))。接下来是计算状态转移的不同代码实现（下面i，j均从0开始）

1. 直接递归

自顶向下：如果原来的三角形有n层，则调用关系树也会有n层，一共有2^n - 1个子问题。子问题重复计算，因此时间效率不高。

/**
    * 递归：没有考虑子问题的重复计算
    * 注意边界
    * @param a
    * @param i
    * @param j
    * @return
    */
   int solver1(int a[][], int i, int j){
       int n = a.length;
       return i == n ? 0 : a[i][j] + Math.max(solver1(a, i+1, j), solver1(a, i+1, j+1));
   }

2. 递推计算

自底向上：d(i+1, j)和d(i+1, j+1)需要在d(i, j)之前完成计算。递推完成后，直接返回辅助数组b[0][0]即可。
时间复杂度为n^2

    /**
    * 递推：自底向上
    * 注意边界
    * @param a
    * @return
    */
   int solver2(int a[][]){
   	   //构造辅助数组b，避免修改原数组a
       int n = a.length;
       int[][] b = new int[n][a[n-1].length];
       for(int j = 0;j<a[n-1].length;j++){
           b[n-1][j] = a[n-1][j];
       }
       
       for(int i = a.length-2;i>=0;i--){
           for(int j = 0;j<a[i].length;j++){
               b[i][j] = a[i][j] + Math.max(b[i+1][j], b[i+1][j+1]);
           }
       }
       return b[0][0];
   }

3. 记忆化搜索

自底向上：时间复杂度为n^2。构造记忆化数组，用于记录已经计算过的子问题。

    /**
   * 记忆化搜索：暴力递归的改进版，仍然是递归，不过保存了计算的中间结果，避免计算重复子问题
   * @param a
   * @return
   */
  int solver3(int a[][], int dp[][], int i, int j){
      if(dp[i][j] > 0){
          return dp[i][j];
      }
      /* 返回赋值语句，否则就等同与第一种方法，子问题重复计算了 */
      return dp[i][j] = a[i][j] + Math.max(solver3(a,dp,i+1,j), solver3(a,dp,i+1,j+1));
  }

主函数输出

需要注意的是第三种记忆化搜索，记忆化数组用来保存已经计算过的状态，因此记忆化数组初始化（Java默认初始化为0）时，-1代表该状态没有被计算。

void solution(){
        int[][]a = {{1},{3, 2},{4, 10 ,1},{4, 3, 2, 20}};
        System.out.println("递归："+solver1(a, 0, 0));
        System.out.println("递推："+solver2(a));

        int n = a.length;
        /* 初始化记忆矩阵 */
        int[][] dp = new int[n][a[n-1].length];
        for(int i = 0;i<dp.length;i++){
            for(int j = 0;j<dp[0].length;j++){
                dp[i][j] = -1;
            }
        }
        for(int j = 0;j<a[n-1].length;j++){
            dp[n-1][j] = a[n-1][j];
        }
        System.out.println("记忆化搜索：" + solver3(a, dp, 0, 0));
    }