金山云笔试21.9.24

金山云笔试21.9.24

代码题：聪明的老鼠

【只A出了这一个，惭愧】

一只聪明的老鼠发现了一个三角形的奶酪迷宫。这个迷宫有若干个小房间，每个小房间有若干块大小相等的小奶酪（每个房间至少有一块奶酪）。 奶酪迷宫的构造如下： (1) 奶酪迷宫一共有N行，第1行有一个小房间，第2行有两个房间，第3行有三个小房间，......第N行有N个小房间。 (2) 所有的小房间都是从第1列开始进行排列的。 (3) 奶酪迷宫的入口是第1行的那个小房间。 (4) 由于奶酪迷宫的特殊构造，小老鼠进入一个房间后，不允许回退到上一层的房间，也不允许走到左边的房间，只允许走到右边或者下面的房间。 (5) 在奶酪迷宫的最后一层，每个房间都有一扇通往迷宫出口的门，且最后一层的小房间没有通往左边和右边小房间的门。 现在小老鼠已经知道了每个小房间里面有多少块小奶酪，它找到了一条可以从入口走到出口且可以得到最多小奶酪的路径。 你能不能编写一个程序，输出小老鼠最多可以得到多少块小奶酪呢？

输入：
3
2
4 5
1 2 3
输出：
13

我的思路：

二维数组存储，每个数据=（本身+上边）或者（本身+左边），取max

需要考虑边界值

注意：最后一行数据只=（本身+上），因为最后一层的小房间没有通往左边和右边小房间的门

package com.lxw.jinshan;

import java.util.Scanner;

public class Main {

    static int n;
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[][] a = new int[110][110];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i+1; j++) {
                int x = scanner.nextInt();
                a[i][j] = x;
            }

        }

        int next = findXXX(a);
        System.out.println(next);

    }

    public static int findXXX(int[][] a){
        
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j <= i; j++) {
                if (i==0&&j==0) continue;
                else if (i==0) ;
                else if (j==0) a[i][j]=a[i-1][j]+a[i][j];
                else a[i][j] = Math.max(a[i-1][j],a[i][j-1])+a[i][j];
            }
        }
        int max = 0;
        for (int j = 0; j < n-1; j++) {
            if (a[n-1][j]+a[n-2][j]>max){
                max=a[n-1][j]+a[n-2][j];
            }
        }
        return max;

    }
}