- 将原问题分解为一系列子问题逐步解决，根据先前的状态求解当前的状态。
- 自底向上的计算顺序，求解当前问题需要保证规模更小的子问题的解已求出。
- 本质上是一种空间换时间的策略，通过记忆化存储的方式避免重复求解相同的子问题，因而往往比递归效率高。
- 空间复杂度往往可以进一步优化，二维数组变一维，一维数组变简单变量。这样做不仅节省空间，时间复杂度可能也会得到一定的常数优化。
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5
的正整数。
根据定义，一个丑数可以由某个更小的丑数乘以2、3或5得到。
问题的关键在于，如何按照从小到大的顺序将丑数一一找出。我们可以用三指针解决这个问题：用三个指针分别指向当前等待乘以2、3、5的丑数，每次取乘积最小的那个得到下一个丑数，然后向后移动必要的指针，保持乘积均大于当前算出的最大丑数，以备后续使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
int p2 = 0, p3 = 0, p5 = 0;
dp[0] = 1;
for (int i = 1; i < n; i++) {
int a = dp[p2] * 2;
int b = dp[p3] * 3;
int c = dp[p5] * 5;
dp[i] = Math.min(Math.min(a, b), c);
if (dp[i] == a) p2++;
if (dp[i] == b) p3++;
if (dp[i] == c) p5++;
}
return dp[n-1];
}
}
|
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[ [2], [3,4], [6,5,7], [4,1,8,3]] 自顶向下的最小路径和为 11（即，2 +
3 + 5 + 1 = 11）。
这题本身就是一道常规的动态规划，不是很难，但是涉及到一个优化的小技巧，我觉得值得记录一下。
正常来说我们应该会从上到下去扫描这个三角形（至少我第一眼是这么去看的），然而其实这里逆向思维一下，从最后一行扫描到第一行，动态规划的过程是等价的，但是这么做会有很多好处：
- 如果我们希望只用一维数组存储动态规划的结果，即实现 \(O(n)\)
的空间复杂度，从下到上计算可以避免中间变量
temp
的使用，因为计算新的 dp[j] 只需要当前的 dp[j]
和 dp[j+1] ，已经被新值覆盖了的 dp[j-1]
不会再被用到。
- 可以避免对每行第一个和最后一个元素的特殊处理。
- 从下到上是三角形收缩的方向，最后返回
dp[0]
即为答案，而从上到下计算则还需要遍历一遍 dp 取最小值。
建议两个方向都写一遍，体会一下其中的微妙差别。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n+1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
|
给定一个整数数组 nums
，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
这道题麻烦的地方就在于存在负数，负负得正，原本的最小值会突然变成最大值。因此不仅要维护当前的最大值，还需要维护一个最小值。在遇到负数时，要先将最大值和最小值交换，这样乘以负数以后大小关系才不会混乱。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int maxProduct(int[] nums) {
int res = Integer.MIN_VALUE;
int max = 1, min = 1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < 0) {
int temp = max;
max = min;
min = temp;
}
max = Math.max(max * nums[i], nums[i]);
min = Math.min(min * nums[i], nums[i]);
res = Math.max(res, max);
}
return res;
}
}
|
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1
的最大正方形，并返回其面积。
若某格为1，则以该格为右下角的最大正方形的边长等于上方的正方形、左边的正方向以及左上方的正方形三者中最小的边长，加上1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int maximalSquare(char[][] matrix) {
int n = matrix.length;
if (n == 0) return 0;
int m = matrix[0].length;
if (m == 0) return 0;
int maxLen = 0;
int[][] dp = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
maxLen = Math.max(maxLen, dp[i][j]);
}
}
}
return maxLen * maxLen;
}
}
|
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。
除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
不同于打家劫舍I和II，这次房屋的排列是树状的，数据结构决定了求解无法像之前那样自底向上进行，只能通过递归来实现，但是其本质依然是动态规划的思想。
我们使用大小为2的数组 res
来表示从当前节点出发可以偷到的最高金额，它有两个状态：res[0]
表示当前节点选择不偷，res[1] 表示当前节点选择偷。我们用
root 表示当前节点，left 和 right
分别表示当前节点的左右孩子节点。由此不难得出下列状态转移方程：
\(\begin{equation} \left\{ \begin{aligned}
\ res[0] &= \max\{left[0],left[1]\} + \max\{right[0], right[1]\} \\
res[1] &= root.val + left[0] + right[0] \\ \end{aligned} \right.
\end{equation}\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public int rob(TreeNode root) {
int[] res = _rob(root);
return Math.max(res[0], res[1]);
}
private int[] _rob(TreeNode root) {
if (root == null) return new int[2];
int[] res = new int[2];
int[] left = _rob(root.left);
int[] right = _rob(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
}
|
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
定义 dp[i][j] 为将子串 word1[1..i]
转换成子串 word2[1..j] 所需要的最小编辑距离。
为此我们有以下三种方式：
- 将
word1[1..i-1] 转换成 word2[1..j] 并删除
word1[i]
- 将
word1[1..i] 转换成 word2[1..j-1] 并插入
word2[j]
- 将
word1[1..i-1] 转换成 word2[1..j-1]
，如果 word1[i] != word2[j] 则将 word1[i]
替换为 word2[j]
由此我们得到状态转移方程：
\(dp[i][j] = \min \begin{cases}
dp[i-1][j]+1 \cr dp[i][j-1]+1 \cr dp[i-1][j-1]+\begin{cases} 0
&if\;word1[i]==word2[j] \cr 1 &otherwise \end{cases}
\end{cases}\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
int[][] dp = new int[n+1][m+1];
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int i = 0; i <= m; i++) dp[0][i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
return dp[n][m];
}
}
|
有 n 个气球，编号为0 到
n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得
nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和
i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right
就变成了相邻的气球。
求所能获得硬币的最大数量。
首先在首尾添加两个数字为1虚拟气球用来处理边界。
定义 dp[i][j] 为戳破 nums[i+1..j-1]
的所有气球所获得的最大收益。我们需要遍历该区间，选定某一个气球
nums[k]
作为最后一个被戳破的气球，使其与两端气球的乘积加上左右两段子区间的收益最大。用状态转移方程表示即：
\(dp[i][j] = \max \limits_{i+1\leq k \leq
j-1} \{dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j]\}\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int maxCoins(int[] nums) {
int n = nums.length + 2;
int[] _nums = new int[n];
_nums[0] = _nums[n-1] = 1;
for (int i = 1; i < n - 1; i++) {
_nums[i] = nums[i-1];
}
int[][] dp = new int[n][n];
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
for (int k = i + 1; k <= j - 1; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + _nums[i] * _nums[k] * _nums[j]);
}
}
}
return dp[0][n-1];
}
}
|
给定一个非空字符串 s 和一个包含非空单词列表的字典
wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
记录下这道题是为了说明动态规划题使用递归来做未必效率更差。
本问题的条件决定了用记忆化递归（自顶向下的动态规划）更加合适，因为不合规的子问题（前缀不在字典中）不会被计算。而如果写成自底向上的动态规划，由于无法预判某个子问题之后是否会被用到，所有的子问题都要被计算一遍并保存起来，导致不必要的时间和空间开销，因而可能会超时或超内存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
HashSet<String> set = new HashSet<>();
HashMap<Integer, List<String>> memo = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
for (String word : wordDict) {
set.add(word);
}
return _wordBreak(s, 0);
}
private List<String> _wordBreak(String s, int start) {
if (memo.containsKey(start)) {
return memo.get(start);
}
List<String> res = new ArrayList<>();
if (start == s.length()) {
res.add("");
return res;
}
for (int end = start; end < s.length(); end++) {
String prefix = s.substring(start, end + 1);
if (set.contains(prefix)) {
List<String> list = _wordBreak(s, end + 1);
for (String e : list) {
if (e.isEmpty()) res.add(prefix);
else res.add(prefix + " " + e);
}
}
}
memo.put(start, res);
return res;
}
}
|
该系列共有6到题，可以参考Leetcode上labuladong写的一篇题解《一个方法团灭
6 道股票问题》，讲得非常棒。