LeetCode 53. 最大子序和
题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路
因为是找连续子数组，因此，用dp[i]来存储以第i个数字为结尾的最大子序列，而dp[i] = max(dp[i-1]+Arr[i], Arr[i])
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size()==0) {
return 0;
}
int n = nums.size();
int dp[n];
int maxnum = dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = INT_MIN;
dp[i] = max(dp[i-1]+nums[i], nums[i]);
maxnum = dp[i] > maxnum ? dp[i] : maxnum;
}
return maxnum;
}
};
LeetCode 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
思路
用数组dpi来存储到达gridi的路径，而dp[i][j] = dp[i-1][j] + dp[i][j-1]，边界情况只需加其中一种即可，而dp[0][0] = 1
代码
class Solution {
public:
int uniquePaths(int m, int n) {
if (m==0 || n==0) {
return 0;
}
int dp[n][m];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i==0&&j==0) {
continue;
}
dp[i][j] = 0;
if (i==0) {
dp[i][j] = dp[i][j-1];
}else if (j==0) {
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
}
return dp[n-1][m-1];
}
};
LeetCode 63. 不同路径II
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
思路
和上一题一样，只要要考虑一下障碍物情况即可。
代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n = obstacleGrid.size();
int m = obstacleGrid[0].size();
long dp[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (obstacleGrid[i][j]==0) {
if (i==0&&j==0) {
dp[i][j] = 1;
continue;
}
dp[i][j] = 0;
if (i==0) {
dp[i][j] = dp[i][j-1];
}else if (j==0) {
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}else{
dp[i][j] = 0;
}
}
}
return dp[n-1][m-1];
}
};
LeetCode 64. 最小路径和
题目
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思路
用dpi来存储到达gridi的最小路径总和，而dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，再考虑一下边界情况即可。
代码
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
int dp[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = 0;
if (i==0&&j==0) {
dp[i][j] = grid[i][j];
continue;
}
if (i==0) {
dp[i][j] = dp[i][j-1] + grid[i][j];
}else if (j==0){
dp[i][j] = dp[i-1][j] + grid[i][j];
}else{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
}
return dp[n-1][m-1];
}
};