1423: 数塔java

1423: 数塔是一道经典的算法问题，通常用于动态规划的练习。在这个问题中，给定一个由数字组成的数塔，从塔的顶部开始，每次只能向下走到相邻的数字上，直到走到塔的底部。要求找出一条路径，使得路径上经过的数字之和最大。

在Java中，可以使用动态规划的思想来解决这个问题。具体的解题步骤如下：

1. 首先，将数塔表示为一个二维数组tower，tower[i][j]表示第i行第j列的数字。
2. 创建一个与数塔大小相同的二维数组dp，dp[i][j]表示从数塔顶部走到第i行第j列时的最大路径和。
3. 从数塔底部开始向上遍历，计算dp数组的值。具体计算方法为：dp[i][j] = tower[i][j] + max(dp[i+1][j], dp[i+1][j+1])，即当前位置的最大路径和等于当前位置的值加上下一行相邻位置的最大路径和中较大的那个。
4. 最后，dp即为所求的最大路径和。

下面是一个示例代码：

public class NumberTower {
    public static int findMaxPath(int[][] tower) {
        int n = tower.length;
        int[][] dp = new int[n][n];
        
        // 初始化最后一行的dp值
        for (int j = 0; j < n; j++) {
            dp[n-1][j] = tower[n-1][j];
        }
        
        // 从倒数第二行开始向上计算dp值
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = tower[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        
        return dp[0][0];
    }
    
    public static void main(String[] args) {
        int[][] tower = {
            {5},
            {8, 4},
            {3, 6, 9},
            {7, 2, 9, 5}
        };
        
        int maxPath = findMaxPath(tower);
        System.out.println("最大路径和为：" + maxPath);
    }
}

这段代码中，我们定义了一个`findMaxPath`方法来计算最大路径和。在`main`方法中，我们给出了一个示例的数塔，并输出了最大路径和。