文章目录
- 1. 买卖股票的最佳时机含冷冻期
- 题干：
- 算法原理：
- 1. 状态表示：
- 2. 状态转移方程
- 3. 初始化
- 4. 填表顺序
- 5. 返回值
- 代码：
- 2. 替换所有的问号
- 题干：
- 算法原理：
- 代码：
1. 买卖股票的最佳时机含冷冻期
原题链接
题干：
整数数组prices
prices[i] 表示第 i 天的股票价格
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)
不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
算法原理：
1. 状态表示：
dp[i][0] 表示：第 i 天结束之后，处于“买入”状态，此时最大利润
dp[i][1] 表示：第 i 天结束之后，处于“可交易”状态，此时最大利润
dp[i][2] 表示：第 i 天结束之后，处于“冷冻期”状态，此时最大利润
2. 状态转移方程
圆圈表示前一天
箭头所指的是当前的状态
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - p[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0] + p[i]
3. 初始化
dp[0][0] = -p[0]
dp[0][1] = 0
dp[0][2] = 0
4. 填表顺序
从左往右
三个表一起填
5. 返回值
max(dp[n-1][1], dp[n-1][2])
代码：
class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n + 1][3];dp[0][0] = -prices[0];for(int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return Math.max(dp[n - 1][1], dp[n - 1][2]);}
}
2. 替换所有的问号
原题链接
题干：
包含小写英文字母和 ‘?’ 字符的字符串 s
将所有的 ‘?’ 转换为若干小写字母
最终的字符串不包含任何 连续重复 的字符
算法原理：
代码：
class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n + 1][3];dp[0][0] = -prices[0];for(int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return Math.max(dp[n - 1][1], dp[n - 1][2]);}
}
