加盟网站制作公司,怎么免费建设个人博客网站,盘锦949公社最新招聘,wordpress优化加速缓存中国动态规划
动态规划的核心思想就是 本次只由上一次决定。
爬楼梯 第3阶由#xff08;第1节2#xff09;和#xff08;第二节1#xff09;#xff0c;不要想着往下迭代#xff0c;不然那是个无穷底。所以f(x)f(x-1)f(x-2) (x2)。所以就是当前只与上个操作相关。
cla…动态规划
动态规划的核心思想就是 本次只由上一次决定。
爬楼梯 第3阶由第1节2和第二节1不要想着往下迭代不然那是个无穷底。所以f(x)f(x-1)f(x-2) (x2)。所以就是当前只与上个操作相关。
class Solution {
public:int climbStairs(int n) {if(n1) return 1;if(n2) return 2;int a 1; //f(x-2)int b 2; //f(x-1)int sum ab;for(int i4;in;i){a b; //更新f(x-2) b sum; //更新f(x-1)sum ab; //f(x) f(x-1)f(x-2)}return sum;}
};杨辉三角 动态规划还是写出哪个公式嘛主要是控制好循环那个i层数字索引。
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint data;if(numRows0) return data;//f(n)(m)f(n-1)(m-1)f(n-1)(m) 差不多就是这个了吧每组第一个和最后一个都是1vectorint d;d.push_back(1);data.push_back(d);for(int i1;inumRows;i){vectorint d;d.push_back(1);for(int j1;ji;j){//f(n)(m)f(n-1)(m-1)f(n-1)(m) 差不多就是这个了吧每组第一个和最后一个都是1d.push_back(data[i-1][j-1]data[i-1][j]);}d.push_back(1);data.push_back(d);}return data;}
};杨辉三角2 what up。 swap(vector1,vector2);可以替换两个这么爽吗。
class Solution {
public:vectorint getRow(int rowIndex) {vectorint d;vectorint data;if(rowIndex 0) {d.push_back(1);return d;}for(int i1;irowIndex;i){swap(data,d); //可以直接转换哈data.clear(); //清空当前需要返回的数据。data.push_back(1);for(int j1;ji;j){data.push_back(d[j-1]d[j]); //f(n)(m) f(n-1)(m-1)f(n-1)(m);}data.push_back(1);}return data;}
};买卖股票的最佳时机 一遍遍历,mindp[i]min(dp[i-1],price[i]) 这里面动态规划的是最小的价格然后再计算最大的利润不是直接的动态规划东西。
class Solution {
public:int maxProfit(vectorint prices) {//一次遍历寻找前面的最小值一遍扫描然后寻找maxprofix//dp(x)min(),然后去计算最大利润也就是前面的最值。vectorint dp(prices.size(),0);int max 0;dp[0] prices[0];for(int i1;iprices.size();i){if(max(prices[i]-dp[i-1])){max (prices[i]-dp[i-1]);}dp[i] min(dp[i-1],prices[i]);}return max;}
};比特位计数 最高位有效mod2为0或者1如果除以2为0的话表示是一样的1数字。如果余数为1的话需要1。
class Solution {
public:vectorint countBits(int n) {//动态规划。//最高或者最低位有效位其实就是找比上前一个多一个1的vectorint data(n1,0);data[0]0;if(n0) return data;data[1]1;for(int i2;in;i){if(i%20) data[i]data[i/2];if(i%21) data[i]data[i/2]1;}return data;}
};
