最后一个点mle了，还能怎么优化？（Java）

Whirlwind @ 2021-03-09 09:34:24

import java.util.Scanner;

 public class Main{
     public static void main(String[] args) {
         Scanner sc=new Scanner(System.in);
         int n=sc.nextInt();
         int dp[][]=new int[n+1][n+1];

         int max=0;
         for(int i=1;i<=n;i++)
             for(int j=1;j<=i;j++) {
                 dp[i][j]=sc.nextInt();
                 dp[i][j]=Math.max(dp[i][j]+dp[i-1][j-1],dp[i][j]+dp[i-1][j]);
                 if(i==n&&dp[n][j]>max) {
                     max=dp[n][j];
                 }
             }

         System.out.println(max);        
     }
 }

by konjacq @ 2021-03-09 09:39:50

换语言

by Surferer @ 2021-03-14 16:47:08

@Whirlwind

个人解法： 定义一个Floor类，用来表示每个层的情况

public static class Floor {
        int size;
        int[] arr = null;

        public Floor(int size) {
            super();
            this.size = size;
            arr = new int[size+2];
        }

        public void print() {
            System.out.println(Arrays.toString(arr));
        }

    }

再用个Floor数组就能表示整个金字塔了

Floor[] pyramid = new Floor[n+1];
        for (int i = 1; i <= n; i++) {
            Floor newFloor = new Floor(i);
            for (int j = 1; j <= i; j++) {
                st.nextToken();
                newFloor.arr[j] = (int) st.nval;
            }
            pyramid[i] = newFloor;
        }

剩下递推每一层情况就行了，代码我就不发了。这样能够避免直接定义一个[n+1][n+1]大小数组所造成的空间浪费。

示例展示：

[0, 7, 0]
[0, 10, 15, 0]
[0, 18, 16, 15, 0]
[0, 20, 25, 20, 19, 0]
[0, 24, 30, 27, 26, 24, 0]

by Whirlwind @ 2021-03-15 19:53:42

@Surferer 了解了！不错的思路