【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结
本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。
买卖股票的题有明显的状态转换，但子序列就没那么明显。
动态规划
买卖股票的最佳时机II
题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。
方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。
参考代码随想录思路解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(2, 0));
dp[0][0] -= prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
}
return dp[len-1][1];
}
};买卖股票的最佳时机III
题意，在[[买卖股票的最佳时机II]]基础上，要求最多只能进行两次股票的购入和卖出。
方法，可以想想此前两题的 dp，dp[i] 代表第 i 天，后面是状态，有两状态就是持有和卖出。换到此题就是状态更多了，故本题可设 5 个状态，0 代表不操作（可省略），1 代表第一次持有（不代表一定购入，可能是之前的购入），2代表第一次卖出，3 是第二次持有，4 是第二次卖出。后面的状态均依赖于自己与前一个状态。
- dp[i][0-4]，意思如上
- 递推公式，对于持有的状态，dp[i][1] = max(dp[i-1][0]-price[i],dp[i-1][1])，就是在不购买的基础上购买当日股票和采用之前购买股票的抉择；对于卖出状态，dp[i][2] = max(dp[i-1][1]+price[i], dp[i-1][2]); 就是在前一日购买股票的基础上，售出当日股票与延续此前卖出的抉择；
- 初始化，dp[0][0] = 0, 不作为当然为 0，dp[0][1] = -1 * price[0]; 购入股票成本, dp[0][2] = 0，马上卖出即无收益；dp[0][3] = -1 * price[0]，当日连续第二次买入; dp[0][4] = 0; 当日连续第二次卖出。
- 遍历方向，从前向后
- 举例……
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int maxProfit(vector<int>& prices) {
// 分五个状态，0 是无操作，1 是第一次持有，2 是第一次卖出，3是第二次持有，4是第二次卖出
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
dp[0][1] -= prices[0];
dp[0][3] -= prices[0];
for (int i = 1; i < prices.size(); i++) {
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];
}
};买卖股票的最佳时机IV
题意，在[[买卖股票的最佳时机III]]基础上，将购买股票的次数由 2 次，拓展为变量 k 次
方法，将dp数组拓展为 price.size() 个 2k+1 的 vector，总共有 2k+1 个状态，其余的思想与方法，同[[买卖股票的最佳时机III]]。
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
// dp[i][0] 为不操作，dp[i][2*k-1] 为第k笔交易持有, dp[i][2*k] 为第k笔交易卖出，k>=1
vector<vector<int>> dp(prices.size(), vector<int>(2*k+1, 0));
// 初始化，对于奇数只是单纯买第一天的负价格，而偶数则是一买就卖的 0
for (int i = 1; i < 2 * k; i+=2) {
dp[0][i] -= prices[0];
}
// 对往后每一行奇偶，分别是前一笔交易与上一天同笔交易的比较
for (int i = 1; i < prices.size(); i++) {
for (int j = 1; j < 2*k+1; j+=2) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i]);
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]+prices[i]);
}
}
return dp[prices.size()-1][2*k];
}
};买卖股票的最佳时机含冷冻期
题意，在 [[买卖股票的最佳时机II]] 可多次买卖股票的基础上，加入冷冻期，即在卖出股票的一天后，才能再买入股票。
方法，引入四种状态，买入，今日卖出，保持卖出，冷冻期。
买入状态可能有前一日的买入状态、保持卖出、冷冻期推出；
今日卖出只会由前一日买入状态卖出今日价格得出；
冷冻期保存前一日的今日卖出状态；
保持卖出则由前一日的保持卖出、冷冻期推出；dp[i][j] 则是 i 天的第 j 个状态
递推公式由上述的文字推出
初始化则是第一日的买入状态为价格负数，其余为零
遍历方向从前到后
举例……参考代码随想录思想的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n==0) return 0;
vector<vector<int>>dp(n, vector<int>(4, 0));
// dp 有四种状态 1 买入；2 今日卖出；3 保持卖出； 4 冷静期
// 3 可能为 2 或 4 的延续
dp[0][0] -= prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i-1][0], max(dp[i-1][2] - prices[i], dp[i-1][3] - prices[i]));
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = max(dp[i-1][2], dp[i-1][3]);
dp[i][3] = dp[i-1][1];
}
return max(dp[n-1][1], max(dp[n-1][2], dp[n-1][3]));
}
};买卖股票的最佳时机含手续费
题意，在[[买卖股票的最佳时机II]]可多次交易的基础上，添加手续费，即每次交易后需扣除一定手续费。
方法，与[[买卖股票的最佳时机II]]的唯一差别在于递推公式，将卖出的部分添加手续费即可。
不过，陆爻齐由于太久没碰相关部分，想自己从零推出来，于是整合了三个状态，写下下面的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
// 我觉着有三种状态
// 第一是直接买入，第二是今日卖出
// 与之前只会多次交易的题相比，多了个手续费，减一下就行了
vector<vector<int>> dp(prices.size(), vector<int>(3, 0));
// 递推公式的话，买入就直接取当日价格负数减下去，卖出则取前一日买入加上这一日卖出
// 初始化，除买入，取0
dp[0][0] -= prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i]);
dp[i][1] = dp[i-1][0] + prices[i] - fee;
dp[i][2] = max(dp[i-1][2], dp[i][1]);
}
// for (int i = 0; i < prices.size(); i++) {
// cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
// }
return max(dp[prices.size()-1][1], dp[prices.size()-1][2]);
}
};看完发现，第三个状态确实可以与第二个状态合并，要追求简洁的情况下，每个状态应是由过去的部分推导出来的，如果有状态与现有状态有关，则可考虑适当合并
于是可以优化成下面的代码，与代码随想录思路相近了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
// 我觉着有三种状态
// 第一是直接买入，第二是今日卖出
// 与之前只会多次交易的题相比，多了个手续费，减一下就行了
vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
// 递推公式的话，买入就直接取当日价格负数减下去，卖出则取前一日买入加上这一日卖出
// 初始化，除买入，取0
dp[0][0] -= prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
}
// for (int i = 0; i < prices.size(); i++) {
// cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
// }
return dp[prices.size()-1][1];
}
};最长递增子序列
题意：给一个数组，求其中最长递增子序列的长度，该子序列可由删除数组中元素得出。
方法：用 dp[i] 表示下标 i 之前的最长递增子序列长度，通过循环得出。
递推公式：dp[i] = max(dp[i], dp[j]+1); j遍历 0 到 i 的元素，该元素数值小于 i 的元素
初始化，均初始化为 1，长度至少为 1；
遍历顺序：从前往后，毕竟是递增
举例：……参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
// dp[i]为地址为 i 的最长子序列长度
int max_len = 1;
// 外循环遍历数组
for (int i = 1; i < nums.size(); i++) {
// 内循环取到已有的最长子序列长度
for (int j = 0; j <= i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j]+1);
}
}
if (dp[i] > max_len) max_len = dp[i];
}
return max_len;
}
};最长连续递增序列
题意：与[[非递减子序列]]相比，要求子序列得是连续的，中间数据不能删。
方法，不需要代码随想录的思路参考，自己都能分析出来。
dp[i] 是下标 i 为末尾的最长连续递增序列长度
递推公式为 dp[i] = dp[i-1]+1; 前提是 dp[i] > dp[i-1]
初始化 全初始化为1
遍历方向从前向后
举例……解法（与代码随想录思路相近）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1); // dp[i] 展示前面某一点到下标 i，最长连续递增子序列长度
int max_len = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i]>nums[i-1]) {
dp[i] = dp[i-1]+1;
if (dp[i] > max_len) max_len = dp[i];
}
}
return max_len;
}
};
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-02-09
【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...
2024-12-08
【Weekly Algorithm】算法周记之《代码随想录》动态规划（四）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，不过周五和周日两门考试太重了，浅做两题，接下来非考试周就继续至少一天一道罢。 本周两道题是完全背包求排列数的应用题和完全背包求 组合/排列 的最小组合数，要记得组合与排列的区别在于背包空间和物品的遍历先后顺序，先遍历物品就不会出现物品乱序填背包的情况，所以是求组合数；而先遍历背包空间，使得同一个空间能有相同物品按不同顺序摆放，则是求排列数。 动态规划 爬楼梯（进阶版） 代码随想录 57. 爬楼梯（第八期模拟笔试） 题意，给 n 个台阶，和一起最多能迈 m 个台阶，问有多少不同方法可爬顶端 方法，由于同一步子可迈多次，故为完全背包问题，而且求的是排列数，与[[组合总和IV]]类似 陆爻齐的解法 123456789101112131415161718192021222324#include <iostream>#include <vector>using namespace std;int main() { int n, m; while(cin...
系列文章