42. 接雨水

题目： 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例:

解题思路

• 使用动态规划(DP)方法求解
• 当前位置接水体积计算公式:$min(Lef{t}_{max},Righ{t}_{max})-CurrHeight$
• 从左到右遍历数组得到每个位置左边柱子高度的最大值$Lef{t}_{max}$；从右到左遍历数组得到每个位置所有右边柱子高度的最大值$Righ{t}_{max}$
  
• 根据得到的每个位置的$Lef{t}_{max}$和$Righ{t}_{max}$， 利用积水量计算公式
  
  如上图黄色标识位置所示：min(leftmax,rightmax)=min(1,3)为1，此时柱子高度为1。所以盛水体积为1。下一个位置 min(leftmax,rightmax)=min(1,3)=1, 此时柱子高度height为0, 根据:min(leftmax,rightmax)-height =1, 此处盛水体积为1

c++ 实现

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);}vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = max(rightMax[i + 1], height[i]);}int ans = 0;for (int i = 0; i < n; i++) {ans += min(leftMax[i], rightMax[i]) - height[i];}return ans;}
};

64. 最小路径和

题目: 给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

解题思路

• 假设dp[i][j]为从起点(左上角点)到grid[i][j]的路径的总数字之和
• 由于每次只能向下或者向右移动，那么dp[i][j]就有:

// 从前一步dp[i-1][j]向下移动grid[i,j]
dp[i][j]=dp[i-1][j] +grid[i][j]
// 或者
//从前一步dp[i][j-1]向右移动grid[i,j]
dp[i][j] = dp[i][j-1]+grid[i][j]

• 此时，每个格子最小取值只能在该格子左端的格子和上端的格子的最小值中取其一公式表示为:dp[i][j] = min(dp[i-1][j] +grid[i][j],dp[i][j-1]+grid[i][j]),根据该公式即可求解

c++ 实现

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

• 由于 1=<m,n<=200, 因此初始化dp[300][300],空间是足够的
• 初始化dp， 由于我们求的是最小值，所以初始化dp为最大值;注意一定要memset(dp,0x3f,sizeof(dp));使用INT_MAX以及1000来初始化结果都出错，可能是会造成Int越界把
• 根据公式dp[i][j] = min(dp[i-1][j] +grid[i][j],dp[i][j-1]+grid[i][j]),所以需要对比向右向下两种情况，取其中最小的。其中当i=0, 此时dp[i][j]，只能由dp[i][j-1]向右移动一步；同理当j=0, 此时dp[i][j], 只能由dp[i-1][j]向下移动一步。所以有:

  for(int i = 0; i < grid.size();i++){for(int j = 0; j < grid[0].size();j++){if(j-1 >=0)dp[i][j] = min(dp[i][j],dp[i][j-1]+grid[i][j]);   if(i-1>=0)dp[i][j] = min(dp[i][j],dp[i-1][j]+grid[i][j]);}}

• 最后返回从左上角到右下角的值: dp[n-1][m-1]

62 不同路径

题目:一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为“Start”）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例:

解题思路

• 由于机器人只能向下和向右走，因此达到指定格子的最后一步，要么是向下要么是向右到达。
• 假设dp[i][j] 表示第i行j列能达到的方案数目，就有 dp[i][j] = dp[i-1][j] + dp[i][j-1](), 即到达指定格子的路径数目就等于到达相邻的上方和左方的两个格子的路径数目之和。

c++ 实现

class Solution {
public:int uniquePaths(int m, int n) {int dp[110][110];memset(dp,0,sizeof(dp));dp[0][0] =1;for (int i=0;i<m;i++){for(int j=0;j<n;j++){if(i>0)dp[i][j] += dp[i-1][j];if (j>0)dp[i][j] += dp[i][j-1];}}return dp[m-1][n-1];}
};

• 对于 i>0且j>0 ,此时到达第i行j列能的方案数目为： dp[i][j] = dp[i-1][j] +dp[i][j-1]。
• 但对于i =0这种情况，只能通过向右移动到达第i行j列，此时该方案数目为: dp[i][j] = dp[i][j-1]; 同理对于j=0时，只能通过向下移动到达第i行j列， 此时该方案数目为：dp[i][j] = dp[i-1][j];因此代码有如下代码:

 for (int i=0;i<m;i++){for(int j=0;j<n;j++){if(i>0)dp[i][j] += dp[i-1][j];if (j>0)dp[i][j] += dp[i][j-1];}}