解题思路:
“向左下走的次数与向右下走的次数相差不能超过 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 人评分
点我有惊喜!你懂得!浏览:1973 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:552 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:1200 |
C语言程序设计教程(第三版)课后习题11.11 (C语言代码)浏览:768 |
C二级辅导-等差数列 (C语言代码)浏览:1213 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:924 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:601 |
A+B for Input-Output Practice (VI) (C语言代码)浏览:552 |
字符串输入输出函数 (C语言代码)浏览:2474 |
C二级辅导-同因查找 (C语言代码)浏览:563 |