Leetcode 简单动态规化53最大子串和，6263不同路径，64最小路径

class Solution { public: int maxSubArray(vector<int>& nums) { int res = nums[0], sum = 0; for(int i=0;i<nums.size();i++){ sum = max(nums[i],sum+nums[i]); res = max(res,sum); } return res; } };

 

这道题目有解析的方案数

其实，本道题在排列组合问题中可化为求C(m+n-2,m-1)（或C(m+n-2,n-1)）。 即一共有m行n列，其中需要向下走m-1步，向右走n-1步，一共走m+n-2步。所以就是在m+n-2步中选出哪m-1步是向下走的，其余自动为向右走的步数。

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