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];
}
}
