动态规划—数塔问题

问题描述： image

如上图（图片来自网络）是一个数塔，从顶部出发在每一个节点都只能走到相邻的节点，也就是只能向左或者向右走，一直走到底层，要求找出一条路径，使得路径上的数字之和最大。

首先需要将具体问题抽象化，即将上面的数塔图先整理成一个二维数组：

int data[N][N] = {
            {9,0,0,0,0},
            {12,15,0,0,0},
            {10,6,8,0,0},
            {2,18,9,5,0},
            {19,7,10,4,16}
        };

然后根据分析这个数塔，再根据这个二维数组进行计算。

解决方案是自底至顶分析，自上而下计算。因此我们从第四层的四个数据开始分析：

• 如果最优路径经过2，那么一定经过19
• 如果最优路径经过18，那么一定经过10
• 如果最优路径经过9，那么一定经过10
• 如果最优路径经过5，那么一定经过16

因此，我们总结出规律：如果最有路径经过当前点，那么从当前点到路径尾节点的数字之和将是当前点的值加上左右孩子其中较大的值，即：

公式1中我们多了个额外的数组int[][] dp，这个数组用来存储最终的结果。有了公式1，代码就很好写了：

public class CB {
    public static void main(String[] args) {
        int data[][] = {
                {9, 0, 0, 0, 0},
                {12, 15, 0, 0, 0},
                {10, 6, 8, 0, 0},
                {2, 18, 9, 5, 0},
                {19, 7, 10, 4, 16}
        };
        int[][] dp = numberTower(data);
        //打印出结果
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        int i = 0, pre = 0;
        System.out.println("选中->" + data[i][pre]);
        for (i = 1; i < dp.length - 1; i++) {
            int node_value = dp[i - 1][pre] - data[i - 1][pre];//默认选中的是左孩子
            if (node_value == dp[i][pre + 1]) {//如果发现选中的是右孩子，那么pre加1
                pre = pre + 1;
            }
            System.out.println("选中->" + data[i][pre]);
        }
    }

    public static int[][] numberTower(int[][] data) {
        int N = data.length;
        int width = data[N - 1].length;
        int[][] dp = new int[N + 1][width];//比原来的数塔多一层傀儡层
        // dp初始化
        for (int i = 0; i < width; ++i) {//需要给倒数第二层初始化赋值
            dp[N - 1][i] = data[N - 1][i];
        }
        for (int i = N - 1; i >= 0; i--)
            for (int j = 0; j < data[i].length - 1; j++)
                dp[i][j] = (dp[i + 1][j] > dp[i + 1][j + 1] ? dp[i + 1][j] : dp[i + 1][j + 1]) + data[i][j];
        return dp;
    }
}

打印结果如下：

[59, 49, 29, 21, 0]
[50, 49, 29, 21, 0]
[38, 34, 29, 21, 0]
[21, 28, 19, 21, 0]
[19, 7, 10, 4, 16]
[0, 0, 0, 0, 0]
选中->9
选中->12
选中->10
选中->18
选中->10