class082 动态规划中用观察优化枚举的技巧-上【算法】-摩杜云开发者社区

class082 动态规划中用观察优化枚举的技巧-上【算法】

class082 动态规划中用观察优化枚举的技巧-上【算法】_算法

class082 动态规划中用观察优化枚举的技巧-上【算法】_动态规划_02

code1 121. 买卖股票的最佳时机

// 买卖股票的最佳时机
// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
// 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票
// 设计一个算法来计算你所能获取的最大利润
// 返回你可以从这笔交易中获取的最大利润
// 如果你不能获取任何利润，返回 0
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

枚举以当前卖出，选择与之前最小的一减就是利润，取最大

package class082;

// 买卖股票的最佳时机
// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票
// 设计一个算法来计算你所能获取的最大利润
// 返回你可以从这笔交易中获取的最大利润
// 如果你不能获取任何利润，返回 0
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
public class Code01_Stock1 {

	public static int maxProfit(int[] prices) {
		int ans = 0;
		for (int i = 1, min = prices[0]; i < prices.length; i++) {
			// min : 0...i范围上的最小值
			min = Math.min(min, prices[i]);
			ans = Math.max(ans, prices[i] - min);
		}
		return ans;
	}

}

code2 122. 买卖股票的最佳时机 II

// 买卖股票的最佳时机 II
// 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格
// 在每一天，你可以决定是否购买和/或出售股票
// 你在任何时候最多只能持有一股股票
// 你也可以先购买，然后在同一天出售
// 返回你能获得的最大利润
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

每一次价格上坡的时候买入，相邻两个比较就好了

package class082;

// 买卖股票的最佳时机 II
// 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格
// 在每一天，你可以决定是否购买和/或出售股票
// 你在任何时候 最多 只能持有 一股 股票
// 你也可以先购买，然后在 同一天 出售
// 返回 你能获得的 最大 利润
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
public class Code02_Stock2 {

	public static int maxProfit(int[] prices) {
		int ans = 0;
		for (int i = 1; i < prices.length; i++) {
			ans += Math.max(prices[i] - prices[i - 1], 0);
		}
		return ans;
	}

}

code3 123. 买卖股票的最佳时机 III

// 买卖股票的最佳时机 III
// 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易
// 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii

不枚举优化：
dp2[i]：[0…i]做两笔交易的最大利润，在i的时候卖出
枚举买入点j，dp1[j]+prices[i]-price[j]

dp1[i]:[0…i]做一笔交易的最大利润
不在i的时候卖出，dp1[i-1]
在i的时候卖出，prices[i]-min(0,i)

枚举优化
引入best数组：
求出0…i范围上，Max(dp1[i]-price[i])
这样：
dp2[i]=best[i]+prices[i]

package class082;

// 买卖股票的最佳时机 III
// 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易
// 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii
public class Code03_Stock3 {

	// 完全不优化枚举的方法
	// 通过不了，会超时
	public static int maxProfit1(int[] prices) {
		int n = prices.length;
		// dp1[i] : 0...i范围上发生一次交易，不要求在i的时刻卖出，最大利润是多少
		int[] dp1 = new int[n];
		for (int i = 1, min = prices[0]; i < n; i++) {
			min = Math.min(min, prices[i]);
			dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
		}
		// dp2[i] : 0...i范围上发生两次交易，并且第二次交易在i时刻卖出，最大利润是多少
		int[] dp2 = new int[n];
		int ans = 0;
		for (int i = 1; i < n; i++) {
			// 第二次交易一定要在i时刻卖出
			for (int j = 0; j <= i; j++) {
				// 枚举第二次交易的买入时机j <= i
				dp2[i] = Math.max(dp2[i], dp1[j] + prices[i] - prices[j]);
			}
			ans = Math.max(ans, dp2[i]);
		}
		return ans;
	}

	// 观察出优化枚举的方法
	// 引入best数组，需要分析能力
	public static int maxProfit2(int[] prices) {
		int n = prices.length;
		// dp1[i] : 0...i范围上发生一次交易，不要求在i的时刻卖出，最大利润是多少
		int[] dp1 = new int[n];
		for (int i = 1, min = prices[0]; i < n; i++) {
			min = Math.min(min, prices[i]);
			dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
		}
		// best[i] : 0...i范围上，所有的dp1[i]-prices[i]，最大值是多少
		// 这是数组的设置完全是为了替代最后for循环的枚举行为
		int[] best = new int[n];
		best[0] = dp1[0] - prices[0];
		for (int i = 1; i < n; i++) {
			best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
		}
		// dp2[i] : 0...i范围上发生两次交易，并且第二次交易在i时刻卖出，最大利润是多少
		int[] dp2 = new int[n];
		int ans = 0;
		for (int i = 1; i < n; i++) {
			// 不需要枚举了
			// 因为，best[i]已经揭示了，0...i范围上，所有的dp1[i]-prices[i]，最大值是多少
			dp2[i] = best[i] + prices[i];
			ans = Math.max(ans, dp2[i]);
		}
		return ans;
	}

	// 发现所有更新行为都可以放在一起
	// 并不需要写多个并列的for循环
	// 就是等义改写，不需要分析能力
	public static int maxProfit3(int[] prices) {
		int n = prices.length;
		int[] dp1 = new int[n];
		int[] best = new int[n];
		best[0] = -prices[0];
		int[] dp2 = new int[n];
		int ans = 0;
		for (int i = 1, min = prices[0]; i < n; i++) {
			min = Math.min(min, prices[i]);
			dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
			best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
			dp2[i] = best[i] + prices[i];
			ans = Math.max(ans, dp2[i]);
		}
		return ans;
	}

	// 发现只需要有限几个变量滚动更新下去就可以了
	// 空间压缩的版本
	// 就是等义改写，不需要分析能力
	public static int maxProfit4(int[] prices) {
		int dp1 = 0;
		int best = -prices[0];
		int ans = 0;
		for (int i = 1, min = prices[0]; i < prices.length; i++) {
			min = Math.min(min, prices[i]);
			dp1 = Math.max(dp1, prices[i] - min);
			best = Math.max(best, dp1 - prices[i]);
			ans = Math.max(ans, best + prices[i]); // ans = Math.max(ans, dp2);
		}
		return ans;
	}

}

code4 188. 买卖股票的最佳时机 IV

// 买卖股票的最佳时机 IV
// 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易
// 也就是说，你最多可以买 k 次，卖 k 次
// 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

不优化方法：
dp[i][j]：做i次交易，0~j范围上的最大利润
最后一笔不在j位置上卖出：dp[i][j-1]
最后一笔在j位置上卖出：
枚举p：最后一笔的买入位置
dp[i-1][p]+prices[j]-prices[p]，0<=p<j

优化枚举
使用best：来表示dp[i-1][p]-prices[p]中的最大值
dp[i][j]=best+prices[j]

package class082;

// 买卖股票的最佳时机 IV
// 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易
// 也就是说，你最多可以买 k 次，卖 k 次
// 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
public class Code04_Stock4 {

	// 就是股票问题2
	public static int free(int[] prices) {
		int ans = 0;
		for (int i = 1; i < prices.length; i++) {
			ans += Math.max(prices[i] - prices[i - 1], 0);
		}
		return ans;
	}

	public static int maxProfit1(int k, int[] prices) {
		int n = prices.length;
		if (k >= n / 2) {
			// 这是一个剪枝
			// 如果k >= n / 2，那么代表所有上坡都可以抓到
			// 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
			return free(prices);
		}
		int[][] dp = new int[k + 1][n];
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j < n; j++) {
				dp[i][j] = dp[i][j - 1];
				for (int p = 0; p < j; p++) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][p] + prices[j] - prices[p]);
				}
			}
		}
		return dp[k][n - 1];
	}

	public static int maxProfit2(int k, int[] prices) {
		int n = prices.length;
		if (k >= n / 2) {
			// 这是一个剪枝
			// 如果k >= n / 2，那么代表所有上坡都可以抓到
			// 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
			return free(prices);
		}
		int[][] dp = new int[k + 1][n];
		for (int i = 1, best; i <= k; i++) {
			best = dp[i - 1][0] - prices[0];
			for (int j = 1; j < n; j++) {
				// 用best变量替代了枚举行为
				dp[i][j] = Math.max(dp[i][j - 1], best + prices[j]);
				best = Math.max(best, dp[i - 1][j] - prices[j]);
			}
		}
		return dp[k][n - 1];
	}

	// 对方法2进行空间压缩的版本
	public static int maxProfit3(int k, int[] prices) {
		int n = prices.length;
		if (k >= n / 2) {
			// 这是一个剪枝
			// 如果k >= n / 2，那么代表所有上坡都可以抓到
			// 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
			return free(prices);
		}
		int[] dp = new int[n];
		for (int i = 1, best, tmp; i <= k; i++) {
			best = dp[0] - prices[0];
			for (int j = 1; j < n; j++) {
				tmp = dp[j];
				dp[j] = Math.max(dp[j - 1], best + prices[j]);
				best = Math.max(best, tmp - prices[j]);
			}
		}
		return dp[n - 1];
	}

}

code5 714. 买卖股票的最佳时机含手续费

// 买卖股票的最佳时机含手续费
// 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格
// 整数 fee 代表了交易股票的手续费用
// 你可以无限次地完成交易，但是你每笔交易都需要付手续费
// 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
// 返回获得利润的最大值
// 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

最后一次交易，i位置不卖出
done
最后一次交易，i位置卖出
prepare+prices[i]

i位置不买
prepare
i位置买
done-prices[i]-fee

package class082;

// 买卖股票的最佳时机含手续费
// 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格
// 整数 fee 代表了交易股票的手续费用
// 你可以无限次地完成交易，但是你每笔交易都需要付手续费
// 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
// 返回获得利润的最大值
// 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
public class Code05_Stack5 {

	public static int maxProfit(int[] prices, int fee) {
		// prepare : 交易次数无限制情况下，获得收益的同时扣掉了一次购买和手续费之后，最好的情况
		int prepare = -prices[0] - fee;
		// done : 交易次数无限制情况下，能获得的最大收益
		int done = 0;
		for (int i = 1; i < prices.length; i++) {
			done = Math.max(done, prepare + prices[i]);
			prepare = Math.max(prepare, done - prices[i] - fee);
		}
		return done;
	}

}

code6 309. 买卖股票的最佳时机含冷冻期

// 买卖股票的最佳时机含冷冻期
// 给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格
// 设计一个算法计算出最大利润
// 在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

i位置不参与买卖
done[i-1]
i位置参与买卖
prepare[i-1]+prices[i]

i位置不参与购买
prepare[i-1]
i位置参与购买
done[i-2]-prices[i],done[i-2]因为有冷静期，所有只能取在前两天之前的收益-今天的购买

package class082;

// 买卖股票的最佳时机含冷冻期
// 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格
// 设计一个算法计算出最大利润
// 在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
public class Code06_Stack6 {

	public static int maxProfit1(int[] prices) {
		int n = prices.length;
		if (n < 2) {
			return 0;
		}
		// prepare[i] : 0...i范围上，可以做无限次交易，获得收益的同时一定要扣掉一次购买，所有情况中的最好情况
		int[] prepare = new int[n];
		// done[i] : 0...i范围上，可以做无限次交易，能获得的最大收益
		int[] done = new int[n];
		prepare[1] = Math.max(-prices[0], -prices[1]);
		done[1] = Math.max(0, prices[1] - prices[0]);
		for (int i = 2; i < n; i++) {
			done[i] = Math.max(done[i - 1], prepare[i - 1] + prices[i]);
			prepare[i] = Math.max(prepare[i - 1], done[i - 2] - prices[i]);
		}
		return done[n - 1];
	}

	// 只是把方法1做了变量滚动更新(空间压缩)
	// 并没有新的东西
	public static int maxProfit2(int[] prices) {
		int n = prices.length;
		if (n < 2) {
			return 0;
		}
		// prepare : prepare[i-1]
		int prepare = Math.max(-prices[0], -prices[1]);
		// done2 : done[i-2]
		int done2 = 0;
		// done1 : done[i-1]
		int done1 = Math.max(0, prices[1] - prices[0]);
		for (int i = 2, curDone; i < n; i++) {
			// curDone : done[i]
			curDone = Math.max(done1, prepare + prices[i]);
			// prepare : prepare[i-1] -> prepare[i]
			prepare = Math.max(prepare, done2 - prices[i]);
			done2 = done1;
			done1 = curDone;
		}
		return done1;
	}

}

code7 903. DI 序列的有效排列

// DI序列的有效排列
// 给定一个长度为n的字符串s，其中s[i]是:
// "D"意味着减少，"I"意味着增加
// 有效排列是对有n+1个在[0,n]范围内的整数的一个排列perm，使得对所有的i：
// 如果 s[i] == ‘D’，那么 perm[i] > perm[i+1]
// 如果 s[i] == ‘I’，那么 perm[i] < perm[i+1]
// 返回有效排列的perm的数量
// 因为答案可能很大，所以请返回你的答案对10^9+7取余
// 测试链接 : https://leetcode.cn/problems/valid-permutations-for-di-sequence/

package class082;

// DI序列的有效排列
// 给定一个长度为n的字符串s，其中s[i]是:
// "D"意味着减少，"I"意味着增加
// 有效排列是对有n+1个在[0,n]范围内的整数的一个排列perm，使得对所有的i：
// 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]
// 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]
// 返回有效排列的perm的数量
// 因为答案可能很大，所以请返回你的答案对10^9+7取余
// 测试链接 : https://leetcode.cn/problems/valid-permutations-for-di-sequence/
public class Code07_DiSequence {

	public static int numPermsDISequence1(String s) {
		return f(s.toCharArray(), 0, s.length() + 1, s.length() + 1);
	}

	// 猜法很妙！
	// 一共有n个数字，位置范围0~n-1
	// 当前来到i位置，i-1位置的数字已经确定，i位置的数字还没确定
	// i-1位置和i位置的关系，是s[i-1] : D、I
	// 0~i-1范围上是已经使用过的数字，i个
	// 还没有使用过的数字中，比i-1位置的数字小的，有less个
	// 还没有使用过的数字中，比i-1位置的数字大的，有n - i - less个
	// 返回后续还有多少种有效的排列
	public static int f(char[] s, int i, int less, int n) {
		int ans = 0;
		if (i == n) {
			ans = 1;
		} else if (i == 0 || s[i - 1] == 'D') {
			for (int nextLess = 0; nextLess < less; nextLess++) {
				ans += f(s, i + 1, nextLess, n);
			}
		} else {
			for (int nextLess = less, k = 1; k <= n - i - less; k++, nextLess++) {
				ans += f(s, i + 1, nextLess, n);
			}
		}
		return ans;
	}

	public static int numPermsDISequence2(String str) {
		int mod = 1000000007;
		char[] s = str.toCharArray();
		int n = s.length + 1;
		int[][] dp = new int[n + 1][n + 1];
		for (int less = 0; less <= n; less++) {
			dp[n][less] = 1;
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int less = 0; less <= n; less++) {
				if (i == 0 || s[i - 1] == 'D') {
					for (int nextLess = 0; nextLess < less; nextLess++) {
						dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
					}
				} else {
					for (int nextLess = less, k = 1; k <= n - i - less; k++, nextLess++) {
						dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
					}
				}
			}
		}
		return dp[0][n];
	}

	// 通过观察方法2，得到优化枚举的方法
	public static int numPermsDISequence3(String str) {
		int mod = 1000000007;
		char[] s = str.toCharArray();
		int n = s.length + 1;
		int[][] dp = new int[n + 1][n + 1];
		for (int less = 0; less <= n; less++) {
			dp[n][less] = 1;
		}
		for (int i = n - 1; i >= 0; i--) {
			if (i == 0 || s[i - 1] == 'D') {
				dp[i][1] = dp[i + 1][0];
				for (int less = 2; less <= n; less++) {
					dp[i][less] = (dp[i][less - 1] + dp[i + 1][less - 1]) % mod;
				}
			} else {
				dp[i][n - i - 1] = dp[i + 1][n - i - 1];
				for (int less = n - i - 2; less >= 0; less--) {
					dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % mod;
				}
			}
		}
		return dp[0][n];
	}

}

2023-12-7 16:10:35