直接用昨天的完全背包推导公式，还是很简单的。 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 &…
509. 斐波那契数 class Solution { public: int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; int a1 = 0, a2 = 1; int a3; for (int i = 0; i < n - 1; i ++) { a3 = a1 + a2…
738. 单调递增的数字 把递减的部分向前借一位，全填9 class Solution { public: // 把后面的数字换成9 int monotoneIncreasingDigits(int n) { string s = to_string(n); int flag = s.size(); for (int i = s.size() - …
435. 无重叠区间 总和 - 不相交的长度 class Solution { public: // 不相交的最大个数 int eraseOverlapIntervals(vector<vector<int>>& intervals) { int n = intervals.size(); int res = 1; …
860. 柠檬水找零 有大的先用大的找零 class Solution { public: // 有大的票子就先花大的票子 bool lemonadeChange(vector<int>& bills) { int cnt1 = 0, cnt2 = 0; for (int i = 0; i < bills.size(); …