动态规划法解决数字三角形用java

动态规划是解决数字三角形问题的一种有效方法。下面是用Java实现数字三角形问题的动态规划算法：

public class Triangle {
    public static void main(String[] args) {
        int[][] triangle = {
            {1},
            {2, 3},
            {4, 5, 6},
            {7, 8, 9, 10}
        };
        int result = maxSum(triangle);
        System.out.println(result);
    }

    public static int maxSum(int[][] triangle) {
        int n = triangle.length;
        int[][] dp = new int[n][n];
        //初始化最后一行
        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = triangle[n - 1][i];
        }
        //从倒数第二行开始向上递推
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }
}

在上面的代码中，我们定义了一个`maxSum`方法，该方法接收一个数字三角形数组作为参数，并返回数字三角形中从顶部到底部的最大和。

我们首先创建一个二维数组`dp`来存储每个位置的最大和。然后，我们初始化`dp`数组的最后一行为数字三角形的最后一行。

接下来，我们从倒数第二行开始向上递推，计算每个位置的最大和。我们使用`dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]`公式来计算每个位置的最大和。该公式表示当前位置的最大和等于下一行相邻两个位置中的最大值加上当前位置的值。

最后，我们返回`dp[0][0]`，即数字三角形的顶部元素的最大和。