动态规划算法核心：

找到“状态”和“选择” -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系。

1. 动态规划解题套路框架

首先，动态规划问题的一般形式就是求最值。既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

其次，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握 递归思维，只有列出 正确的「状态转移方程」，才能正确地穷举。

而且，你需要判断算法问题是否 具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。

另外，动态规划问题 存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要你使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

重叠子问题、最优子结构、状态转移方程就是动态规划三要素。在实际的算法问题中，写出状态转移方程是最困难的。

明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

1.1 斐波那契数列

题目：「斐波那契数」

1.1.1 暴力递归

1
2
3
4
int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

思维过程：

  • 递归树：想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。

  • 时间复杂度：子问题个数乘以解决一个子问题需要的时间。子问题个数为 O(2 n )。然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。所以，这个算法的时间复杂度为二者相乘，即 O(2 n )，指数级别。

    由于存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。

1.1.2 带备忘录的递归解法

造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fib(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return dp(memo, N);
}

// 带着备忘录进行递归
int dp(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题的个数。

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。

解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。

所以，本算法的时间复杂度是 O(n)。

「自顶向下」：从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。

「自底向上」：反过来，我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。

1.1.3 dp 数组的迭代（递推）解法

1
2
3
4
5
6
7
8
9
10
11
12
int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

这个 DP table 特别像之前那个「剪枝」后的结果，只是反过来算而已。

拓展延伸

「状态转移方程」：

img

你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。

可见列出「状态转移方程」的重要性，它是解决问题的核心，而且很容易发现，其实状态转移方程直接代表着暴力解法。

千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。

更进一步：当前状态 n 只和之前的 n-1, n-2 两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行。把空间复杂度降为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fib(int n) {
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // 分别代表 dp[i - 1] 和 dp[i - 2]
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2;
        // 滚动更新
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

1.2 凑零钱问题

题目：「零钱兑换」

1.2.1 暴力递归

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？

假设你有面值为 1, 2, 5 的硬币，你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10, 9, 6 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1, 2, 5 的硬币），求个最小值，就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。

既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

1、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

2、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

3、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。

所以我们可以这样定义 dp 函数：dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。

那么根据这个定义，我们的最终答案就是 dp(amount) 的返回值。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 伪码框架
int coinChange(int[] coins, int amount) {
    // 题目要求的最终结果是 dp(amount)
    return dp(coins, amount);
}

// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(int[] coins, int n) {
    // 做选择，选择需要硬币最少的那个结果
    for (int coin : coins) {
        res = min(res, 1 + dp(coins, n - coin));
    }
    return res;
}

加上 base case 即可得到最终的答案：

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
class Solution {
    public int coinChange(int[] coins, int amount) {
        // 题目要求的最终结果是 dp(amount)
        return dp(coins, amount);
    }

    // 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
    int dp(int[] coins, int amount) {
        // base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);
            // 子问题无解则跳过
            if (subProblem == -1) continue;
            // 在子问题中选择最优解，然后加一
            res = Math.min(res, subProblem + 1);
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

「状态转移方程」：

img

1.2.2 带备忘录的递归

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
class Solution {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
        Arrays.fill(memo, -666);

        return dp(coins, amount);
    }

    int dp(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        // 查备忘录，防止重复计算
        if (memo[amount] != -666)
            return memo[amount];

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);
            // 子问题无解则跳过
            if (subProblem == -1) continue;
            // 在子问题中选择最优解，然后加一
            res = Math.min(res, subProblem + 1);
        }
        // 把计算结果存入备忘录
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}

很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn).

1.2.3 dp 数组的迭代解法

dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 数组大小为 amount + 1，初始值也为 amount + 1
        Arrays.fill(dp, amount + 1);

        // base case
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                // 子问题无解，跳过
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}

1.3 总结

第一个斐波那契数列的问题，解释了如何通过「备忘录」或者「dp table」的方法来优化递归树，并且明确了这两种方法本质上是一样的，只是自顶向下和自底向上的不同而已。

第二个凑零钱的问题，展示了如何流程化确定「状态转移方程」，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题而已。

计算机解决问题其实没有任何特殊的技巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。

列出状态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门。

2. 最长递增子序列 LIS

题目：最长递增子序列

动态规划法的核心思想是 数学归纳法。假如我们想证明一个数学结论，那么先假设这个结论在 k < n 时成立，然后根据这个假设，想办法推导证明出 k = n 的时候此结论成功。如果能证明出来，那么就说明这个结论对于 k 等于任何数都成立。

类似，我们设计动态规划算法，需要一个 dp 数组，可以假设 dp[0 ... i-1] 都已经算出来了，然后：怎么通过这些结果计算出 dp[i]?

a. 状态：

b. 选择：

c. dp[i]: 表示以 nums [i] 这个数结尾的最长递增子序列的长度。

d. base case: dp [i] 初始化值为 1，因为以 nums [i] 结尾的最长递增子序列起码要包含自己。

e. 最终结果:dp[n]表示以nums[n]结尾的最长递增子序列的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLIS(int[] nums) {
        int size = nums.length;
        // 实例化并初始化dp数组
        int[] dp = new int[size];
        Arrays.fill(dp, 1);
        
        // 遍历状态i
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < i; k++) {
                // nums[i] 能和 dp[k] 构成递增序列，注意此处的dp[k]不一定是[0,i-1]中最大的
                if (nums[i] > nums[k]) {
                    dp[i] = Math.max(dp[i], dp[k] + 1);
                }
            }
        }
        int maxLength = Arrays.stream(dp).max().orElse(0);
        return maxLength;
}

3. 信封嵌套问题

题目：俄罗斯套娃信封问题

题解：先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。

先对这些数对进行排序：

1

然后在 h 上寻找最长递增子序列：

2

对于宽度 w 相同的数对，要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的，逆序排序保证在 w 相同的数对中最多只选取一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {
    int n = envelopes.length;
    // 按宽度升序排列，如果宽度一样，则按高度降序排列
    Arrays.sort(envelopes, new Comparator<int[]>() 
    {
        public int compare(int[] a, int[] b) {
            return a[0] == b[0] ? 
                b[1] - a[1] : a[0] - b[0];
        }
    });
    // 对高度数组寻找 LIS
    int[] height = new int[n];
    for (int i = 0; i < n; i++)
        height[i] = envelopes[i][1];

    return lengthOfLIS(height);
}

4. 最大子数组和问题

题目：最大子数组和

a. 状态：

b. 选择：要么与前面的相邻子数组连接，形成一个更大的数组；要么不与前面的子数组连接，自己作为一个子数组。

c. dp[i]: 表示以 nums [i] 这个数结尾的最大子数组和。

d. base case: dp [0] = nums[0]，表示：第一个元素前面没有子数组

e. 最终结果:dp[n-1]表示以nums[n-1]结尾的最长递增子序列的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    // base case
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i],nums[i] + dp[i-1]);
    }

    int res = Integer.MIN_VALUE;
    for(int i = 0; i < n; i++) {
        res = Math.max(res,dp[i]);
    }
    return res;
}

5. 最优子结构及 dp 遍历方向

具备最优子结构才能够使用动态规划算法从最简单的子问题递推出复杂问题的解；

a. 从左到右，从上倒下

1
2
3
4
5
6
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
		dp[i][j] = ... ...
	}
}

b. 从右到左，从下到上

1
2
3
4
5
6
int[][] dp = new int[m][n];
for (int i = m-1; i >= 0; i--) {
	for (int j = n-1; j >= 0; j--) {
		dp[i][j] = ... ...
	}
}

c. 从左上到右下，从左到右

1
2
3
4
5
6
7
8
9
10
11
12
13
// 针对dp[n][n]，且对角线上的数据为base case,值都为1 
for (int l = 2; l <= n; l++) {
	for (int i = 0; i <= n-l; i++) {
		j = l + i - 1;
		dp[i][j] = ... ...
	}
}

for (int i = n-2; i >= 0; i--) {
	for (int j = i+1; j < n; j++) {
		dp[i][j] = ... ...
	}
}

6. 最长公共子序列

题目：「最长公共子序列」

a. 状态：

b. 选择：如果s1[i-1]等于s2[j-1],则dp[i][j] = dp[i-1][j-1] + 1

c. dp[i][j]: 对于s1[0···i-1]和s2[0···j-1]，它们的LCS长度是dp[i][j]

d. base case: dp[0][··]和dp[··][0]都应该初始化为0

e. 最终结果:dp[m][n]表示s1和s2的最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

7. 编辑距离

题目：编辑距离

a. 状态：

b. 选择：如果s1[i-1]等于s2[j-1],则dp[i][j] = dp[i-1][j-1] ;如果s1[i-1]不等于s2[j-1]，则dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)

c. dp[i][j]: 对于s1[0···i]和s2[0···j]，它们的最小编辑距离是dp[i][j]

d. base case: dp[i][0] = i和dp[0][j] = j

e. 最终结果:dp[m][n]表示s1和s2的最小编辑距离

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
public int minDistance(String word1, String word2) {
   int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    //初始化，相当于 word1 为空字符串，变成 word2时，用添加的操作
    for (int i = 0; i <= n; i++) {
        dp[0][i] = i;
    }

    //初始化，相当于 word1的字符串，变成word2空字符串，全部删除自己，用删除的操作
    for (int j = 0; j <= m; j++) {
        dp[j][0] = j;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int modCount = 0;
            if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                modCount = 1;
            }

            dp[i][j] = Math.min(Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1), dp[i - 1][j - 1] + modCount);
        }
    }

    return dp[m][n];
}

8. 最长回文子序列

8.1 一维dp数组

dp[i]:以array[i]为结尾的最长递增子序列的长度。

1
2
3
4
5
6
7
8
int n = array.length;
int[] dp = new int[n];

for (int i = 1; i < n; i++) {
	for (int j = 1; j < i; j++) {
		dp[i] = 最值（dp[i],dp[j]··· ···）;
	}
}

8.2 二维dp数组

1
2
3
4
5
6
7
8
9
10
11
12
int n = array.length;
int[][] dp = new int[n][n];

for (int i = 1; i < n; i++) {
	for (int j = 1; j < n; j++) {
		if (arr[i] == arr[j]) {
			dp[i][j] = dp[i][j] + ···;
		} else {
			dp[i][j] = 最值（··· ···）;
		}
	}
}
  • dp[i][j]:在子数组arr1[0···i]和子数组arr2[0···j]中，要求的子序列长度为dp[i][j]
  • dp[i][j]:在子数组arr[i···j]中，要求的子序列的长度为dp[i][j]

8.3 最长回文子序列

题目：最长回文子序列

a. 状态：

b. 选择：如果s[i]等于s[j],则dp[i][j] = dp[i+1][j-1]+2 ;如果s[i]不等于s[j]，则dp[i][j] = max(dp[i+1][j],dp[i][j-1])

c. dp[i][j]: 在子串s[i···j]中，最长回文子序列的长度为dp[i][j]

d. base case: dp[i][i] = 1

e. 最终结果:dp[0][n-1]表示s的最长回文子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] f = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        f[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                f[i][j] = f[i + 1][j - 1] + 2;
            } else {
                f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
            }
        }
    }
    return f[0][n - 1];
}

9. 状态压缩：对动态规划进行降维打击

10. 以最小插入次数构造回文串

题目：以最小插入次数构造回文串

a. 状态：

b. 选择：如果s[i]等于s[j],则dp[i][j] = dp[i+1][j-1];如果s[i]不等于s[j]，则dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1

c. dp[i][j]: 在子串s[i···j]中，最少插入dp[i][j]次插入才能变成回文串

d. base case: dp[i][i] = 0

e. 最终结果:dp[0][n-1]表示字符串s最少插入dp[0][n-1]次才能变成回文串

1
2
3
4
5
6
7
8
9
10
11
public int minInsertions(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1];
            else dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
        }
    }
    return dp[0][n - 1];
}

11. 正则表达式匹配

题目：正则表达式匹配

a. 状态：

b. 选择：

c. dp[i][j]:

d. base case:

e. 最终结果:

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
public boolean isMatch(String s, String p) {
    int m = s.length();
    int n = p.length();

    boolean[][] f = new boolean[m + 1][n + 1];
    f[0][0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') {
                f[i][j] = f[i][j - 2];
                if (matches(s, p, i, j - 1)) {
                    f[i][j] = f[i][j] || f[i - 1][j];
                }
            } else {
                if (matches(s, p, i, j)) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
    }
    return f[m][n];
}

public boolean matches(String s, String p, int i, int j) {
    if (i == 0) {
        return false;
    }
    if (p.charAt(j - 1) == '.') {
        return true;
    }
    return s.charAt(i - 1) == p.charAt(j - 1);
}

12. 四个键盘

题目：四个键的键盘

1
2
3
4
5
6
7
8
9
10
11
12
public int maxA(int n) {
    int[] dp = new int[n + 1];
    for (int i = 0; i < n + 1; ++i) {
        dp[i] = i;
    }
    for (int i = 3; i < n + 1; ++i) {
        for (int j = 2; j < i - 1; ++j) {
            dp[i] = Math.max(dp[i], dp[j - 1] * (i - j));
        }
    }
    return dp[n];
}

13. 高楼扔鸡蛋

题目：鸡蛋掉落

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
class Solution {
    private int[][] f;

    public int superEggDrop(int k, int n) {
        f = new int[n + 1][k + 1];
        return dfs(n, k);
    }

    private int dfs(int i, int j) {
        if (i < 1) {
            return 0;
        }
        if (j == 1) {
            return i;
        }
        if (f[i][j] != 0) {
            return f[i][j];
        }
        int l = 1, r = i;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            int a = dfs(mid - 1, j - 1);
            int b = dfs(i - mid, j);
            if (a <= b) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return f[i][j] = Math.max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1;
    }
}

14. 戳气球

题目：戳气球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = 1;
    arr[n + 1] = 1;
    System.arraycopy(nums, 0, arr, 1, n);
    int[][] f = new int[n + 2][n + 2];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 2; j <= n + 1; j++) {
            for (int k = i + 1; k < j; k++) {
                f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + arr[i] * arr[k] * arr[j]);
            }
        }
    }
    return f[0][n + 1];
}

快来参与讨论吧~

博客近期分类标签归档
项目软件开发人工智能Staller
社交友链
更多关于本站
本站由 卡卡龙 使用 Stellar 1.29.1主题创建

本站访问量 次. 本文阅读量 次.

Stellar Copyright Licenses Hexo 备案 描述文字 描述文字