53. 最大子序和

題目描述

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

解題思路

dp數(shù)組：dp[i]代表以nums[i]結(jié)尾的連續(xù)子數(shù)組的最大和
狀態(tài)轉(zhuǎn)移：若新加入的數(shù)nums[i]使得和變小了，則取dp[i]為nums[i]；反之，取dp[i-1] + nums[i]

代碼實現(xiàn)

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

        //dp[i]代表以nums[i]結(jié)尾的連續(xù)子數(shù)組的最大和
        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 網(wǎng)格的左上角 （起始點在下圖中標記為 “Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為 “Finish” ）。
問總共有多少條不同的路徑？

解題思路

dp數(shù)組：dp[i][j]表示從start到達第i行、第j列的路徑條數(shù)
base case：當網(wǎng)格只有一行或一列時，只有1條路徑
狀態(tài)轉(zhuǎn)移：到達第i行、第j列的路徑有兩類。第一種是，先到達第i-1行第j列，再向下一格；第二種是，先到達第1行第j-1列，再向右一格。因此 dp[i][j] = dp[i - 1][j] + dp[i][j-1];

代碼實現(xiàn)

class Solution {
    public int uniquePaths(int m, int n) {
        /dp[i][j]表示從start到達第i行、第j列的路徑條數(shù)
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                //base case,當網(wǎng)格只有一行或一列時，只有1條路徑
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                    continue;
                }
                //狀態(tài)轉(zhuǎn)移
                dp[i][j] = dp[i - 1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

63. 不同路徑 II

問題描述

一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。

解題思路

沿用上一題的動態(tài)規(guī)劃思路，加入對障礙物的判斷即可

代碼實現(xiàn)

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        //dp[i][j]表示從start到達第i行、第j列的路徑條數(shù)
        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
                //當網(wǎng)格只有一行或一列，并且前面沒有障礙物時，有1條路徑
                //當網(wǎng)格只有一行或一列，并且前面有障礙物時，無法到達
                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;
                }
                //狀態(tài)轉(zhuǎn)移
                dp[i][j] = dp[i - 1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}