[数据结构与算法]剑指 offer day9

剑指 Offer 42. 连续子数组的最大和

题目：

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

题解：

官方题解

1. 遍历nums[i]，判断 nums[i]和nums[i]+前面i-1和的最大值 的大小；
2. pre用于维护前面i-1个子数组和的最大值；
3. 假设以下标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];  
    }