西安做网站建设的公司,中高端网站设计,网站建设需要用到的软件,wordpress 全文字主题动态规划算法8
LeetCode 123 买卖股票的最佳时机-iii 2023.12.13
题目链接代码随想录讲解[链接]
int maxProfit(vectorint prices) {//1确定dp二维数组//dp[i][0]表示遍历到第i天时第一次持有股票的当前收入;dp[i][1]表示遍历到第i天时第一次未持有股票的当前…动态规划算法8
LeetCode 123 买卖股票的最佳时机-iii 2023.12.13
题目链接代码随想录讲解[链接]
int maxProfit(vectorint prices) {//1确定dp二维数组//dp[i][0]表示遍历到第i天时第一次持有股票的当前收入;dp[i][1]表示遍历到第i天时第一次未持有股票的当前收入//dp[i][2]表示遍历到第i天时第二次持有股票的当前收入;dp[i][3]表示遍历到第i天时第二次未持有股票的当前收入vectorvectorint dp(prices.size(), vectorint(4, 0));//3初始化第一天第一次与第二次持有股票的收入为-prices[0]其他值为0dp[0][0] -prices[0];dp[0][2] -prices[0];//2确定递推公式4确定遍历顺序for (int i 1; i prices.size(); i){//第i天第一次持有股票的收入max(股票不卖(上一天第一次持有股票的收入)第一次买完今天的股票的收入)dp[i][0] max(dp[i-1][0], -prices[i]);//第i天第一次未持有股票的收入max(上一天第一次未持有股票的收入今天第一次卖股票的收入dp[i][1] max(dp[i-1][1], dp[i-1][0]prices[i]);//第i天第二次持有股票的收入max(股票不卖(上一天第二次持有股票的收入)第二次买完今天的股票的收入)dp[i][2] max(dp[i-1][2], dp[i-1][1]-prices[i]);//第i天第二次未持有股票的收入max(上一天第二次未持有股票的收入今天第二次卖股票的收入dp[i][3] max(dp[i-1][3], dp[i-1][2]prices[i]);}//输出答案为最后一天第二次未持有股票的结果return dp[prices.size()-1][3];
}LeetCode 188 买卖股票的最佳时机-iv 2023.12.13
题目链接代码随想录讲解[链接]
int maxProfit(int k, vectorint prices) {//1确定dp二维数组//dp[i][0]表示遍历到第i天时第一次持有股票的当前收入;dp[i][1]表示遍历到第i天时第一次未持有股票的当前收入//dp[i][2*j]表示遍历到第i天时第j1次持有股票的当前收入;dp[i][2*j1]表示遍历到第i天时第j1次未持有股票的当前收入vectorvectorint dp(prices.size(), vectorint(2*k, 0));//3初始化第一天第一次到第k次持有股票的收入为-prices[0]其他值为0for (int i 0; i 2*k; i 2)dp[0][i] -prices[0];//2确定递推公式4确定遍历顺序for (int i 1; i prices.size(); i){for (int j 0; j 2*k; j 2){//第i天第一次持有股票的收入max(股票不卖(上一天第一次持有股票的收入)第一次买完今天的股票的收入)if(j 0)dp[i][j] max(dp[i-1][j], -prices[i]);//第i天第j次持有股票的收入max(股票不卖(上一天第j次持有股票的收入)第j次买完今天的股票的收入)elsedp[i][j] max(dp[i-1][j], dp[i-1][j-1]-prices[i]);//第i天第j次未持有股票的收入max(上一天第j次未持有股票的收入今天第j次卖股票的收入dp[i][j1] max(dp[i-1][j1], dp[i-1][j]prices[i]);}}//输出答案为最后一天第k次未持有股票的结果return dp[prices.size()-1][2*k-1];
}
