LeetCode： 剑指 Offer 47. 礼物的最大价值
入门级 dp 题 1 找状态 2 转移方程 3 初始状态 4 返回值
dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1])
public int maxValue(int[][] grid) { int r = grid.length; int c = grid[0].length; int[][] dp = new int[r][c]; dp[0][0] = grid[0][0]; for (int i = 1; i < r; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int i = 1; i < c; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } // 下、右 for (int i = 1; i < r; i++) { for (int j = 1; j < c; j++) { dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]); } } return dp[r - 1][c - 1]; } public static void main(String[] args) { int[][] arr = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; Offer47 o = new Offer47(); System.out.println(o.maxValue(arr)); }
