动态规划解决数塔问题_本关任务:编写用动态规划解决数塔问题。

一、题目
如图所示，将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字.……第n层有n个数子。现在要从第一层走到第n层，每次只能走向下一层的接连两个数字的其中一个，问：最后将路径上所有数字相加后得到的和最大是多少？

二、动态规划解法
设ele[i][j]表示第i层的第j个元素，max[i][j]表示从第i层第j个元素出发的到达最底层的所有路径中能得到的最大和。那么max[i][j]的值就是从max[i+1][j]和max[i+1][j+1]取最大值再加上ele[i][j]，所以的到递推公式：max[i][j] = max{max[i+1][j]，max[i+1][j+1]}+ele[i][j]。对于最后一层元素，max[n-1][j] = ele[n-1][j]。最终只要从最底层递推到第一层，max[0][0]就是所求的结果。
三、代码（Java）

public static int tower(int n,int[][] ele) throws Exception{
        if(n<0||ele==null){
            throw new Exception("参数错误！");
        }
        int[][] max = new int[n][n];//记录以当前元素开始的最大路径和
        //最后一层，max[n][i]和ele[n][i]相等
        for(int i=0;i<n;i++){
            max[n-1][i] = ele[n-1][i];
        }
        //开始递推，直到最顶层的元素
        for(int j=n-2;j>=0;j--){
            for(int k=0;k<=j;k++){
                max[j][k] = Math.max(max[j+1][k],max[j+1][k+1])+ele[j][k];
            }
        }
        return max[0][0];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17