代码随想录 day37|day38|day39

贪心续
合并区间
题意：将重合的区间合并。
思路：先把区间按照左端点排序。之后使用一个st表示左端点，ed表示右端点，如果区间是分离的那么就把先的区间加入到集合。
代码

 struct comp
    {
        bool operator()(const vector<int> &lhs ,const vector<int> &rhs)
        {
            if(lhs[0]<rhs[0])
            {
                return true  ; 
            }
            return false ; 
        }
    } ; 
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        vector<vector<int>> res ; 
        sort(intervals.begin() , intervals.end() , comp()) ;
        int l =  intervals[0][0], r = intervals[0][1] ; 
        for(int i = 1 ; i <  intervals.size();  ++i)
        {
            if(intervals[i][0]<= r)
            {
                if(r< intervals[i][1])
                r = intervals[i][1] ; 
            }
            else if(intervals[i][0]> r)
            {
                res.push_back(vector<int>{l,r}) ; 
                l = intervals[i][0] ;
                r= intervals[i][1] ; 
            }
        }
        res.push_back(vector<int>{l,r}) ; 
        return res ; 

动态规划
动态规划五部曲：
1.进行对动规数组表示的定义。一维表示，二维表示 。
2.对动规数组进行初始化。
3.对状态转移的方程进行定义。
4.确定动规的遍历顺序
5.打印动规数组。
动规基础
斐波那契数
思路：
1.dp[i] 表示第i个斐波那契数。
2.动规数组初始化，dp[0] = 0 ， dp[1] = 1 ;
3.状态转移方程定义：dp[i] = dp[i-1] + dp[i-2] ;
4.确定动规的遍历顺序是从小到大。
5.打印dp数组。
爬楼梯
思路：
1.dp[i] 表示到第i层楼梯的爬法。
2.动态规划的数组的初始化。dp[1] = 1 , dp[2] =2 ;
3.动态转移方程：dp[i] = dp[i-1] + dp[i-2] ; // 第i层的楼爬法是 dp[i-1]爬法 + dp[i-2] 爬法;
4.遍历方向从小到大。
5.打印dp数组。
代码

class Solution {
public:
    int climbStairs(int n)
     {
        const int N = 47 ;
        int dp[N]  = {0};
        dp[1] = 1 , dp[2] =2 ; 
        for(int i =3 ; i<=n ; ++ i)
        {
            dp[i] = dp[i-1] + dp[i-2] ; 
        }   
        return dp[n] ; 
    }
};

使用最小花费爬楼梯
1.dp[i] 表示爬到第i层的花费。
2.dp[] 全部初始化为0 。
3.遍历顺序从i=0到i=9 。
4.状态转移 dp[i] = dp[i-1] + cost[i-1] ; dp[i] = dp[i-2] + cost[i-2] ; 这是在dp[i-1] + cost[i-1] 和dp[i-2] + cost[i-2] 相比较的情况下。 表示到第i层时的花费。
5.打印dp数组

   int minCostClimbingStairs(vector<int>& cost) 
    {
        const int  N = 1000  + 10 ; 
        int dp[N] = {0} ; 

        for(int i = 2; i<=cost.size() ; ++ i)
        {
            if(dp[i-1] + cost[i-1] < dp[i-2] + cost[i-2])
            dp[i] += dp[i-1] + cost[i-1] ; // 支付的费用最少表示
            else 
            dp[i]  += dp[i-2] + cost[i-2] ; 
        }
        return  dp[cost.size()] ; 
    }

[不同路径]（https://leetcode.cn/problems/unique-paths/description/）
题意：一个机器人从左上角到右下角的总共有多少条路径。
思路：
1.dp[i][j] 表示：从左上角到i，j点的多少条路径。
2.因为机器人到边缘永远是一条路径，所以x=0 时 所有的元素都为0 。 y=0 时，所有的元素都为0。
3.状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1] 是因为机器人从上方或者左方来的
4.遍历顺序从上往下，从左往右
5.打印dp数组

      const int N = 110 ;
        int dp[N][N] = {0};
        for(int i = 1; i <= m  ; ++ i )
        {
            dp[i][1] = 1 ; 
        }
        for(int i = 1; i <= n  ; ++ i )
        {
            dp[1][i] = 1 ; 
        }
        for(int i = 2 ; i <=m ; ++ i )
            for(int j = 2 ; j <= n ;++ j)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] ; 
            }
        return dp[m][n] ;
    ````
 [不同路径2](https://leetcode.cn/problems/unique-paths-ii/description/) 
 题意：从起点到终点问有多少条路径，并且中间有个石头。 要绕过石头的路径。
 思路：
 1.dp[i][j] 表示：从左上角到i，j点的多少条路径。
 2.2.因为机器人到边缘永远是一条路径，所以x=0 时 所有的元素都为0 。 y=0 时，所有的元素都为0。  因为如果石头在这条边缘那么这个石头之后的路都走不了。这也要加入到初始化中
 3.状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1] ; if(obstacleGrid[i][j] == 1) continue ; 
 4.遍历顺序依然是从上往下，从左往右
 5.打印dp数组
 代码

     const int N = 110 ;
    int dp[N][N] = {0};
    int m = obstacleGrid.size() ;
    int n = obstacleGrid[0].size() ; 
    for(int i = 0 ; i<m && obstacleGrid[i][0] == 0; ++ i)
    {
        dp[i][0] = 1 ; 
    }
     for(int j = 0 ; j< n && obstacleGrid[0][j] == 0 ; ++ j)
     {
        dp[0][j] = 1 ; 
     }
    for(int i = 1 ; i<m ; ++ i)
        for(int j = 1 ; j< n ; ++ j)
        {
            if(obstacleGrid[i][j] ==1 )
            {
                continue ; 
            }
            dp[i][j] = dp[i-1][j] + dp[i][j-1] ; 
        }
    return dp[m-1][n-1] ;