day-36 代码随想录算法训练营（19）part05

435.无重叠区间

思路：首先对数组排序，只需要关注重叠区间就行，有重叠时计数+1，然后更新当前右边界为重叠区间中的最小右边界。

763.划分字母区间

思路：记录每一个字母的最远位置，然后从头开始遍历，不断更新最远位置，当i等于最远位置时，说明这个区间内的字母在后面不会再出现；此时最远距离-起始位就是区间长度，然后更新起始位到下一位。

56.合并区间

思路：先对区间进行排序，临时空间保存第一个区间。然后判断是否重叠，存在重叠时更新临时空间最大右边界；不存在重叠时，把临时区间添加进结果，然后对临时空间清空，再保存当前区间，作为下一次判断的起始区间。

 746.使用最小花费爬楼梯

思路：每一可以爬一个楼梯或者两个楼梯，就在两种情况中找最小值

注意：每一个位置的花费当往上爬才累加

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();int dp[n+1];dp[1]=dp[0]=0;//第一步是不需要花费的for(int i=2;i<=n;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);//每一个位置的花费都加上了}return dp[n];}
};

62.不同路径

思路：

• 1.首先确定dp存储的是，到达第 i 个位置的所有路径数

• 2.初始化，第一行和第一列的每个位置都只有一条路径到达

• 3.递推式   dp[i][j]+=dp[i][j-1]+dp[i-1][j] （累加是因为每到一个位置，路径的数量都在递增）

• 4.遍历顺序：直接从前往后遍历

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>dp(m,vector<int>(n,0));for(int i=0;i<n;i++)//第一行每个位置都只有一种走法dp[0][i]=1;for(int i=0;i<m;i++)//第一列每个位置都只有一种走法dp[i][0]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]+=dp[i][j-1]+dp[i-1][j];//每个位置只有从左边来和上边来}}return dp[m-1][n-1];}
};