7.6 背包问题
1143. Longest Commom Subsequence (Medium)
Input: text1 = "abcde", text2 = "ace"
Output: 3
ace
dpdp[i]i idp
dpdp[i][j]i j
int longestCommonSubsequence(string text1, string text2) { int m = text1.length(), n = text2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) {
if (text1[i-1] == text2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1;
} else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
} }
} return dp[m][n];
}
7.6
NPNW wv
010-1
dp[i][j]ij ijidp[i][j]
= dp[i-1][j]ii-1i iwvdp[i][j] = dp[i-1][j-w] + v
O¹NWº
int knapsack(vector<int> weights, vector<int> values, int N, int W) { vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; ++i) {
int w = weights[i-1], v = values[i-1];
for (int j = 1; j <= W; ++j) { if (j >= w) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
} else { dp[i][j] = dp[i-1][j];
} }
} return dp[N][W];
}

7.2:0-1
0-1
-
O¹Wº
i = 2w = 2v = 3jdp[2][j]
= max(dp[1][j], dp[1][j-2] + 3)
i = 1
dpidp[j]
= max(dp[j], dp[j-w] + v)
i-1dp[j-w]dp[j-w]
ji
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
vector<int> dp(W + 1, 0);
for (int i = 1; i <= N; ++i) {
int w = weights[i-1], v = values[i-1];
for (int j = W; j >= w; --j) {
dp[j] = max(dp[j], dp[j-w] + v);
return dp[W];

7.3:
-
i = 2
w = 2v = 3j = 52 dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)
O¹NWº
dp[2][3]dp[1][3]dp[2][1]
dp[2][1]dp[1][1]
dp[2][3]dp[2][5] = max(dp[1][5], dp[2][3] + 3)
dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)0-1
i-1
i
int knapsack(vector<int> weights, vector<int> values, int N, int W) { vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; ++i) {
int w = weights[i-1], v = values[i-1];
for (int j = 1; j <= W; ++j) { if (j >= w) {
dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v);
} else { dp[i][j] = dp[i-1][j];
} }
} return dp[N][W];
O¹Wº j-w
int knapsack(vector<int> weights, vector<int> values, int N, int W) { vector<int> dp(W + 1, 0);
for (int i = 1; i <= N; ++i) { int w = weights[i-1], v = values[i-1];
for (int j = w; j <= W; ++j) { dp[j] = max(dp[j], dp[j-w] + v);
} }
return dp[W];
}
0-1
416. Partition Equal Subset Sum (Medium)
Input: [1,5,11,5] Output: true
[1,5,5][11]
0-1sum sum/2
bool canPartition(vector<int> &nums) { int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2) return false;
int target = sum / 2, n = nums.size();
vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
for (int i = 0; i <= n; ++i) { dp[i][0] = true;
} for (int i = 1; i <= n; ++i) {
for (int j = nums[i-1]; j <= target; ++j) { dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
bool canPartition(vector<int> &nums) { int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2) return false;
int target = sum / 2, n = nums.size();
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int i = 1; i <= n; ++i) { for (int j = target; j >= nums[i-1]; --j) {
dp[j] = dp[j] || dp[j-nums[i-1]];
} }
return dp[target];
}
474. Ones and Zeroes (Medium)
m0n10-1
mn01
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3 Output: 4
5031[10,0001,1,0]
0-101
// int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (const string & str: strs) { auto [count0, count1] = count(str);
for (int i = m; i >= count0; --i) { for (int j = n; j >= count1; --j) {
dp[i][j] = max(dp[i][j], 1 + dp[i-count0][j-count1]);
return dp[m][n];
}
// pair<int, int> count(const string & s){
int count0 = s.length(), count1 = 0;
for (const char & c: s) { if (c == ’1’) {
++count1;
--count0;
} }
return make_pair(count0, count1);
}
322. Coin Change (Medium)
-1
Input: coins = [1, 2, 5], amount = 11 Output: 3
11 = 5 + 5 + 1
dpamount + 2-1 -1-1i
amount + 11amount + 2
-1
int coinChange(vector<int>& coins, int amount) { if (coins.empty()) return -1;
vector<int> dp(amount + 1, amount + 2);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) { for (const int & coin : coins) {
if (i >= coin) { dp[i] = min(dp[i], dp[i-coin] + 1);
全站分卷索引 · 68 卷
- 11 题目分类
- 22 最易懂的贪心算法
- 32.3 区间问题
- 42.4 练习
- 53 玩转双指针
- 63.2 Two Sum
- 73.4 快慢指针
- 83.5 滑动窗口
- 93.6 练习
- 104 居合斩!二分查找
- 114.3 查找区间
- 124.4 旋转数组查找数字
- 134.5 练习
- 145 千奇百怪的排序算法
- 155.2 快速选择
- 165.3 桶排序
- 175.4 练习
- 186 一切皆可搜索
- 196.3 回溯法
- 206.4 广度优先搜索
- 216.5 练习
- 227 深入浅出动态规划
- 237.3 基本动态规划:二维
- 247.4 分割类型题
- 257.5 子序列问题
- 267.6 背包问题
- 277.7 字符串编辑
- 287.8 股票交易
- 297.9 练习
- 308 化繁为简的分治法
- 318.3 练习
- 329 巧解数学问题
- 339.4 数字处理
- 349.5 随机与取样
- 359.6 练习
- 3610 神奇的位运算
- 3710.3 二进制特性
- 3810.4 练习
- 3911 妙用数据结构
- 4011.2 数组
- 4111.3 栈和队列
- 4211.4 单调栈
- 4311.5 优先队列
- 4411.6 双端队列
- 4511.7 哈希表
- 4611.8 多重集合和映射
- 4711.9 前缀和与积分图
- 4811.10 练习
- 11.10
- 566. Reshape the Matrix (Easy)
- 225. Implement Stack using Queues (Easy)
- 503. Next Greater Element II (Medium)
- 217. Contains Duplicate (Easy)
- 697. Degree of an Array (Easy)
- 594. Longest Harmonious Subsequence (Easy)
- 287. Find the Duplicate Number (Medium)
- 313. Super Ugly Number (Medium)
- 870. Advantage Shuffle (Medium)
- 307. Range Sum Query - Mutable (Medium)
- 4912 令人头大的字符串
- 5012.3 字符串理解
- 5112.4 字符串匹配
- 5212.5 练习
- 5313 指针三剑客之一:链表
- 5413.3 其它链表技巧
- 5513.4 练习
- 5614 指针三剑客之二:树
- 5714.3 层次遍历
- 5814.4 前中后序遍历
- 5914.5 二叉查找树
- 6014.6 字典树
- 6114.7 练习
- 14.7
- 226. Invert Binary Tree (Easy)
- 617. Merge Two Binary Trees (Easy)
- 572. Subtree of Another Tree (Easy)
- 404. Sum of Left Leaves (Easy)
- 513. Find Bottom Left Tree Value (Easy)
- 538. Convert BST to Greater Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Easy)
- 530. Minimum Absolute Difference in BST (Easy)
- 889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)
- 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
- 94. Binary Tree Inorder Traversal (Medium)
- 6215 指针三剑客之三:图
- 6315.3 拓扑排序
- 6415.4 练习
- 6516 更加复杂的数据结构
- 6616.3 复合数据结构
- 6716.4 练习
- 6817 后记