织梦php网站,网站建设比较好公司,怎样创建网站赚钱,宝塔安装wordpress无法访问一#xff1a;题目 二:上码
class Solution {
public:/**思路:1.动态规划五步走1:确定dp数组以及下标的含义因为题目给出至多完成两笔交易 那么我们一天的状态就有5种0 无操作1 第一次买入2 第一次卖出3 第二次买入4 第二次卖出dp[i][j] 表示的是在第i天 [0,4] 其中某个…
一题目 二:上码
class Solution {
public:/**思路:1.动态规划五步走1:确定dp数组以及下标的含义因为题目给出至多完成两笔交易 那么我们一天的状态就有5种0 无操作1 第一次买入2 第一次卖出3 第二次买入4 第二次卖出dp[i][j] 表示的是在第i天 [0,4] 其中某个状态下 已经所剩下的钱2:确定dp数组递推公式dp[i][1] 表示的是第i天,买入股票的状态;那么这个状态我们可以是买入的状态也可以是不买入沿用上一天的状态;- 买入股票的话 那么就证明我们以后还得卖出 所以就是用我们剩下的钱减去它:dp[i][1] dp[i-1][0] - prices[i];//因为我们不能连续操作所以我们上一天状态的是无操作- 不买入股票的话 那么我们就可以知道的是 我们就是昨天的状态 dp[i][1] dp[i-1][1];- 那么我们dp[i][1]到底该如何取值呢?当然是取最大值dp[i][1] max(dp[i-1][0] - prices[i],dp[i-1][1]);dp[i][2] 表示的是第i天 卖出股票的状态 我们可以选择卖出 当然也可以选着没有操作 - 卖出股票了 那就证明我们挣钱了 就是在今天 我们可以经prices[i]收入囊中dp[i][2] dp[i-1][1] prices[i];//这里的dp[i-1][1] 这里的j1 是因为 我们可能前一天买入了//当然也有可能 前一天也沿用更前一天的状态; 但是j ! 2//因为连续两天不能都是卖出的状态- 没卖出 有可能 后几天比今天的价格更高 dp[i][2] dp[i-1][2]//每卖出的话 我们的状态就可以和前面的状态一样 因为我们并不是连续操作的dp[i][2] max(dp[i-1][1]prices[i],dp[i-1][2]);同理我们可以得出:dp[i][3] max(dp[i-1][2] - prices[i],dp[i-1][3]);dp[i][4] max(dp[i-1][3] - prices[i],dp[i-1][4]);3:确定dp数组的初始化初始化也就是在第0天的操作dp[0][0] 0;dp[0][1] -prices[i];//因为目前手里还没钱 所以我们卖出的话肯定是负数dp[0][2] 0; //首先卖出的话我们肯定是赚钱的 因为我们还获取不到前一天的状态 所以 dp[0][2] 0dp[0][3] -prices[i];dp[0][4] 0;4:确定dp数组的遍历顺序dp[i]依赖于昨天的状态 所以是正序5:举例验证**/int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(),vectorint(5,0)); //dp(行,列)dp[0][1] -prices[0];dp[0][3] -prices[0];for (int i 1; i prices.size(); i) {//天数// max(买入,没操作)// max(卖出,没操作) dp[i][1] max(dp[i-1][0] - prices[i],dp[i-1][1]);dp[i][2] max(dp[i-1][1] prices[i],dp[i-1][2]);dp[i][3] max(dp[i-1][2] - prices[i],dp[i-1][3]);dp[i][4] max(dp[i-1][3] prices[i],dp[i-1][4]);}return dp[prices.size()-1][4];}
};慢慢来吧 慢慢进步吧 冰冻三尺非一日之寒
