本文主要是介绍代码随想录 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] ;
这篇关于代码随想录 day37|day38|day39的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
