两个都是买股票 123. 买卖股票的最佳时机 III 用很多数字来表示状态 class Solution { public: // 0 没有操作 // 1 第一次持股 // 2 第一次不持股 // 3 第二次持股 // 4 第二次不持股 int maxProfit(vector<int>& prices) { int n = p…
这两个可以都不用dp的做法写 121. 买卖股票的最佳时机 只能买卖一次。 class Solution { public: int maxProfit(vector<int>& prices) { int res = 0, num = prices[0]; for (int i = 1; i < prices.size(…
三个打家劫舍 198. 打家劫舍 每个点选或不选，每个状态由上一个转移而来 class Solution { public: int rob(vector<int>& nums) { int res = 0; int n = nums.size(); vector<vector<int>> dp(n, v…
139. 单词拆分 完全背包，某一特定的排列 class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int n = s.size(); unordered_set<string>uset(wordDict.begin…
直接用昨天的完全背包推导公式，还是很简单的。 322. 零钱兑换 class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); vector<int> dp(amount + 1, 1e9…
完全背包 在 01背包 的基础上，每个物品可以选任意个。 完全背包的推导公式是这样的： // 二维 for (int i = 1; i <= n; i ++) for (int j = w[i]; j <= m; j ++) f[i][j] = max(f[i-1][j], f[i][j - w[i]] + v[i]); // 一维 /…
1049. 最后一块石头的重量 II 分成两堆，一起碰撞，两堆相减 class Solution { public: // 分成两堆，尽可能满 sum/2 int lastStoneWeightII(vector<int>& stones) { int n = stones.size(); int sum = 0; for (c…
二维dp数组可以转换成一维数组，不过要从后往前，是为了用到的都是上一层的。 416. 分割等和子集 与计数类的题目不同，这题dp的含义是bool值，使用下标为 i 及其前面的能否到达容量为 j。 class Solution { public: // 非计数, 存放bool值 // dp[i][j] 前i个能否把容量变成j // dp[i][j] …
343. 整数拆分 数组表示一个集合，由于可能出现两个或多个相乘，所以递推的公式是 dp[i] = max(dp[i], j * dp[i-j]); dp[i] = max(dp[i], j * (i-j)); // dp[i] = dp[x] * dp[i-x] class Solution { public: int integerBreak(…
矩形路径问题 62. 不同路径 class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(n + 1, vector<int>(m + 1)); dp[1][1] = 1; for (int i = 1; i &…