LowStar


私信TA

用户名:dotcpp0594299

访问量:719

签 名:

等  级
排  名 9001
经  验 1110
参赛次数 0
文章发表 5
年  龄 0
在职情况 学生
学  校 佛山科学技术学院
专  业

  自我简介:

解题思路:

    “向左下走的次数与向右下走的次数相差不能超过 1”,所以你无论怎么走,终点都必定落在最后一行的中间位置

        最后一行是偶数行,那就是落在中间两个数

        奇数行,那就是中间那个数

        所以我是从下往上开始动态规划

        不能走的点设置成false就行,一开始只有最后一行的中间的数才是true,然后逐步往上更新能走的点
注意事项:

参考代码:

import java.util.Scanner;

public class Main{
    private static int[][] arr = new int[100][100];
    private static boolean[][] flag = new boolean[100][100];
    private static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j = 0; i--) {
            for (int j = 0; j <= i; j++) {
                boolean tempFlag = false;
                int left = 0;
                int right = 0;
                if (flag[i+1][j]) {
                    tempFlag = true;
                    left = arr[i+1][j];
                }
                if(flag[i+1][j+1]){
                    tempFlag = true;
                    right = arr[i+1][j+1];
                }
                if(tempFlag){
                    flag[i][j] = true;
                    arr[i][j] += Math.max(left,right);
                }
            }
        }

//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j <= i; j++) {
//                System.out.print(arr[i][j] + " ");
//            }
//            System.out.println();
//        }
        System.out.println(arr[0][0]);
    }
}


 

0.0分

1 人评分

  评论区