剑指 Offer 42. 连续子数组的最大和
题目：
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
题解：
官方题解
- 遍历
nums[i]，判断nums[i]和nums[i]+前面i-1和的最大值的大小； pre用于维护前面i-1个子数组和的最大值；- 假设以下标i为结尾的子数组最大值为f(i)，则f(i) = max{
nums[i],nums[i]+pre}，f(i)继续作为f(i+1)的pre
public int maxSubArray(int[] nums) {
int pre = 0, max = nums[0];for (int x : nums) {
pre = Math.max(pre + x, x);max = Math.max(max, pre);}return max;}
剑指 Offer 47. 礼物的最大价值
题目：
在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
题解：
上面和左边的最大值加上当前值作为到达该点的最大值。
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) continue;if(i == 0) grid[i][j] += grid[i][j - 1] ;else if(j == 0) grid[i][j] += grid[i - 1][j];else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);}}return grid[m - 1][n - 1];}
62. 不同路径
题目：
一个机器人位于一个 m x n 网格的左上角
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角
问总共有多少条不同的路径？
题解：
动态规划 - 不同路径
我们令 dp[i] [j]是到达 i, j 最多路径
动态方程：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]
注意：对于第一行 dp[0] [j]，或者第一列 dp[i] [0]，由于都是在边界，所以只能为 1
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];for (int i = 0; i < n; i++) dp[0][i] = 1;for (int i = 0; i < m; i++) dp[i][0] = 1;for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1]; }