51nod--1083 矩阵取数问题

题目描述

---

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注 一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。 例如：3 * 3的方格。

1 3 3 2 1 3 2 2 1

能够获得的最大价值为：11。 Input 第1行：N，N为矩阵的大小。(2 <= N <= 500) 第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000) Output 输出能够获得的最大价值。 Input示例 3 1 3 3 2 1 3 2 2 1 Output示例

11

解题思想

---

/*、 非常经典的一个动态规划问题，本题采用记忆话搜索 */

---

代码

---

import java.util.Scanner; public class Main{ //preprocess static int[][] map = null; static int[][] a = null; static int n = 0; public static void main(String[] args){ Scanner sc = new Scanner(System.in); //input n = sc.nextInt(); //init a = new int[n][n]; map = new int[n][n]; for(int i=0; i<n; ++i) for(int j=0; j<n; ++j){ a[i][j] = sc.nextInt(); map[i][j] = -1; } //process int result = solve(0,0); //output System.out.println(result); } public static int solve(int i, int j) { if (i == n || j == n) return 0; if (map[i][j] > 0) return map[i][j]; return map[i][j] = Math.max(solve(i + 1, j), solve(i, j + 1)) + a[i][j]; } }