动态规划-三角形

青旅半醒 2023-07-20 05:39 17阅读 0赞

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为 0 - 99

输入格式:

7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

要求输出**最大和**  
往下往右走找出最大的数值和

import java.util.*;
    public class ll {
        
    public static int maxSumUsingDp2(int[][] triangle){
        
            int rowCount = triangle.length;
            int columnCount = triangle[rowCount-1].length;
            int []dp=new int[columnCount];
            for (int k = 0; k <columnCount ; k++) {
        
                dp[k]=triangle[rowCount-1][k];
    
            }
            for (int k = rowCount-2; k >=0 ; k--) {
        
                for (int l = 0; l <=k ; l++) {
        
                    dp[l]=triangle[k][l]+Math.max(dp[l],dp[l+1]);
                }
            }
            return dp[0];
        }
        public static int maxSumUsingDp(int[][] triangle){
        
            int rowCount = triangle.length;
            int columnCount = triangle[rowCount-1].length;
            int [][]dp=new int[rowCount][columnCount];
            for (int k = 0; k <columnCount ; k++) {
        
                dp[rowCount-1][k]=triangle[rowCount-1][k];
            }
            for (int k = rowCount-2; k >=0 ; k--) {
        
                for (int l = 0; l <=k ; l++) {
        
                    dp[k][l]=triangle[k][l]+Math.max(dp[k+1][l],dp[k+1][l+1]);
                }
            }
            return dp[0][0];
        }
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            int [][] tra={
        
                    {
        7},
                    {
        3,8},
                    {
        8,1,0},
                    {
        2,7,4,4},
                    {
        4,5,2,6,5}
            };
            System.out.println(maxSumUsingDp(tra));
        }
    }