121. 买卖股票的最佳时机 - 力扣（LeetCode）(很水)

class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0;int pre = prices[0];for(auto & x : prices){pre = min(pre,x);ans = max(ans, x - pre);}return ans;}
};

64. 最小路径和 - 力扣（LeetCode）

(很水) + 1 

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(0 == i && 0 == j)continue;if(0 == i) grid[i][j] += grid[i][j - 1];else if(0 == j)grid[i][j] += grid[i - 1][j];else grid[i][j] += min(grid[i][j - 1],grid[i - 1][j]);}}         return grid[m - 1][n - 1];}
};

62. 不同路径 - 力扣（LeetCode）

和上一题想法一样,不过可以直接推答案

class Solution {
public:int uniquePaths(int m, int n) {using i64 = int64_t;i64 ans = 1;int x = n, y = 1;while(y < m){ans = ans * x / y;x++;y++;}return ans;}
};

63. 不同路径 II - 力扣（LeetCode） 

 不额外开数组的方法

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n;j++){obstacleGrid[i][j] ^= 1;if(!i && !j)continue;else if(!i) {if(obstacleGrid[i][j] == 0)continue;obstacleGrid[i][j] += obstacleGrid[i][j - 1] - 1;}else if(!j){if(obstacleGrid[i][j] == 0)continue;obstacleGrid[i][j] += obstacleGrid[i - 1][j] - 1;}else {if(obstacleGrid[i][j] == 0)continue;obstacleGrid[i][j] += (obstacleGrid[i][j - 1] + obstacleGrid[i - 1][j]) - 1;}}}return obstacleGrid[m - 1][n - 1];}
};

    或者额外开一个数组

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();vector <int> dp(m, 0);dp[0] = 1 - obstacleGrid[0][0];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if(obstacleGrid[i][j] == 1)dp[j] = 0;else if(j && obstacleGrid[i][j - 1] == 0)//无需判断j == 0dp[j] += dp[j - 1];   }}return dp.back();}
};