【D12】最大子序和&不同路径Ⅰ/Ⅱ (LC 53&62&63)

53. 最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解题思路

dp数组：dp[i]代表以nums[i]结尾的连续子数组的最大和
状态转移：若新加入的数nums[i]使得和变小了，则取dp[i]为nums[i]；反之，取dp[i-1] + nums[i]

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int max = nums[0];

        //dp[i]代表以nums[i]结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];

        for(int i = 1; i < len; i++){
            int sum = dp[i-1] + nums[i];
            dp[i] = Math.max(sum, nums[i]);
            max = Math.max(max,dp[i]);
        }    
        return max;
    }
}

62. 不同路径

问题描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

解题思路

dp数组：dp[i][j]表示从start到达第i行、第j列的路径条数
base case：当网格只有一行或一列时，只有1条路径
状态转移：到达第i行、第j列的路径有两类。第一种是，先到达第i-1行第j列，再向下一格；第二种是，先到达第1行第j-1列，再向右一格。因此 dp[i][j] = dp[i - 1][j] + dp[i][j-1];

代码实现

class Solution {
    public int uniquePaths(int m, int n) {
        /dp[i][j]表示从start到达第i行、第j列的路径条数
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                //base case,当网格只有一行或一列时，只有1条路径
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                    continue;
                }
                //状态转移
                dp[i][j] = dp[i - 1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

63. 不同路径 II

问题描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

解题思路

沿用上一题的动态规划思路，加入对障碍物的判断即可

代码实现

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        //dp[i][j]表示从start到达第i行、第j列的路径条数
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                //有障碍物的格子无法到达，
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                    continue;
                }
                //base case
                //当网格只有一行或一列，并且前面没有障碍物时，有1条路径
                //当网格只有一行或一列，并且前面有障碍物时，无法到达
                if(i == 0 || j == 0){
                    if(i != 0 && dp[i-1][0] == 0){
                        dp[i][j] = 0;
                    }else if(j != 0 && dp[0][j-1] == 0){
                        dp[i][j] = 0;
                    }else{
                        dp[i][j] = 1;
                    }  
                    continue;
                }
                //状态转移
                dp[i][j] = dp[i - 1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}