7.3 基本动态规划:二维
num[i] - num[i-1] = num[i-1] - num[i-2]dpi
dp
int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size();
if (n < 3) return 0;
vector<int> dp(n, 0);
for (int i = 2; i < n; ++i) { if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
dp[i] = dp[i-1] + 1;
} }
return accumulate(dp.begin(), dp.end(), 0);
}
7.3
64. Minimum Path Sum (Medium)
mn
Input:
[[1,3,1], [1,5,1],
[4,2,1]] Output: 7
1->3->1->1->1
dpdp[i][j](i, j)
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]grid
int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) {
dp[i][j] = grid[i][j];
} else if (i == 0) { dp[i][j] = dp[i][j-1] + grid[i][j];
} else if (j == 0) { dp[i][j] = dp[i-1][j] + grid[i][j];
} else { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
} }
} return dp[m-1][n-1];
}
dpdp ijj-1dp[j-1]dp[i][j-1]
dp[j]i-1dp[i-1][j]
int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size();
vector<int> dp(n, 0);
for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) {
if (i == 0 && j == 0) { dp[j] = grid[i][j];
} else if (i == 0) { dp[j] = dp[j-1] + grid[i][j];
} else if (j == 0) { dp[j] = dp[j] + grid[i][j];
} else { dp[j] = min(dp[j], dp[j-1]) + grid[i][j];
} }
} return dp[n-1];
}
542. 01 Matrix (Medium)
010
0-10
Input:
[[0,0,0],
[1,1,1]]
Output:
[[0,0,0], [0,1,0],
[1,2,1]]
O¹mnº
2 2
1O¹m n ºdpmemoization
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { if (matrix.empty()) return {};
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> dp(n, vector<int>(m, INT_MAX - 1));
for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) {
if (matrix[i][j] == 0) { dp[i][j] = 0;
} else { if (j > 0) {
dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
} if (i > 0) {
dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
} }
} }
for (int i = n - 1; i >= 0; --i) { for (int j = m - 1; j >= 0; --j) {
if (matrix[i][j] != 0) { if (j < m - 1) {
dp[i][j] = min(dp[i][j], dp[i][j+1] + 1);
} if (i < n - 1) {
dp[i][j] = min(dp[i][j], dp[i+1][j] + 1);
} }
} }
return dp;
}
221. Maximal Square (Medium)
0-11
0-1
Input:
[["1","0","1","0","0"], ["1","0","1","1","1"],
["1","1","1","1","1"], ["1","0","0","1","0"]]
Output: 4
dp dp[i][j](i, j)
(i, j)10dp[i][j]0
2
1dp[i][j] = kdp[i-1][j-1]dp[i][j-1]dp[i-1][j]
2
| ¹k | 1º | (i, j) | k |
|---|---|---|---|
| k 1 | (i, j) | k |

7.1:542 -0-1dp3
int maximalSquare(vector<vector<char>>& matrix) { if (matrix.empty() || matrix[0].empty()) {
return 0;
} int m = matrix.size(), n = matrix[0].size(), max_side = 0;
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 (matrix[i-1][j-1] == ’1’) { dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
max_side = max(max_side, dp[i][j]);
return max_side * max_side;
全站分卷索引 · 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 后记