以下列举 5 道中等难度和 5 道高难度的动态规划算法题：

中等难度动态规划算法题

1. 最长上升子序列（LIS）

• 题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。例如，输入 nums = [10,9,2,5,3,7,101,18]，输出 4，因为最长上升子序列是 [2,3,7,101]。
• 思路：定义状态 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度，对于每个 i，遍历 0 到 i - 1 的元素 j，如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)，最后答案是 dp 数组中的最大值。

1. 不同路径

• 题目描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？例如，m = 3，n = 2，从左上角到右下角总共有 3 条路径：
  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右
• 思路：定义状态 dp[i][j] 表示到达位置 (i, j) 的不同路径数，边界条件 dp[0][0] = 1，对于 i > 0 且 j > 0，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，对于第一行 dp[0][j] = 1，第一列 dp[i][0] = 1。

1. 零钱兑换

• 题目描述：给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。例如，coins = [1, 2, 5]，amount = 11，输出 3，因为 11 = 5 + 5 + 1。
• 思路：定义状态 dp[i] 表示凑成金额 i 所需的最少硬币个数，初始化为 amount + 1（一个很大的值），dp[0] = 0。对于每个金额 i，遍历所有硬币 coin，如果 i >= coin，则 dp[i] = min(dp[i], dp[i - coin] + 1)，最后如果 dp[amount] > amount 则返回 -1，否则返回 dp[amount]。

1. 最大子序和

• 题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。例如，输入 nums = [-2,1,-3,4,-1,2,1,-5,4]，输出 6，因为连续子数组 [4,-1,2,1] 的和最大，为 6。
• 思路：定义状态 dp[i] 表示以 nums[i] 结尾的最大子序和，dp[i] = max(dp[i - 1] + nums[i], nums[i])，最后答案是 dp 数组中的最大值。

1. 编辑距离

• 题目描述：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。可以对一个单词进行以下三种操作：插入一个字符、删除一个字符、替换一个字符。例如，word1 = "horse"，word2 = "ros"，输出 3，操作步骤为：horse -> rorse (将 'h' 替换为 'r')，rorse -> rose (删除 'r')，rose -> ros (删除 'e')。
• 思路：定义状态 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最少操作数。如果 word1[i - 1] == word2[j - 1]，则 dp[i][j] = dp[i - 1][j - 1]；否则 dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1)（分别对应替换、删除、插入操作）。

高难度动态规划算法题

1. 戳气球

• 题目描述：有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币，其中 left 和 right 是 i 相邻的两个气球的序号。 注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。求所能获得硬币的最大数量。假设 nums = [3,1,5,8]，输出 167，戳破的顺序为 [1,5,8,3] 时可以获得最大硬币数 (3 * 1 * 5) + (3 * 5 * 8) + (1 * 8 * 3) + (3 * 1 * 1) = 167。
• 思路：定义状态 dp[i][j] 表示戳破 i 到 j 之间（包括 i 和 j）的所有气球能获得的最大硬币数。通过枚举最后一个戳破的气球 k，将问题分解为 dp[i][j] = max(dp[i][j], dp[i][k - 1] + nums[i - 1] * nums[k] * nums[j + 1] + dp[k + 1][j])，其中 i <= k <= j。

1. 最大正方形

• 题目描述：在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。例如，输入矩阵 matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]，输出 4，因为最大正方形的边长为 2。
• 思路：定义状态 dp[i][j] 表示以 (i, j) 为右下角的最大正方形的边长。如果 matrix[i][j] == '1'，则 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1，否则 dp[i][j] = 0。最后答案是 dp 数组中的最大值的平方。

1. 买卖股票的最佳时机 IV

• 题目描述：给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，以及一个整数 k 。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。例如，k = 2，prices = [2,4,1]，输出 2，可以在第 1 天买入，第 2 天卖出，利润为 4 - 2 = 2。
• 思路：定义状态 dp[i][j][0] 表示在第 i 天进行了 j 笔交易且当前不持有股票的最大利润，dp[i][j][1] 表示在第 i 天进行了 j 笔交易且当前持有股票的最大利润。通过状态转移方程 dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])，dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]) 进行计算，边界条件需要特殊处理。

1. 单词拆分 II

• 题目描述：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。例如，s = "pineapplepenapple"，wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]，输出 ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]。
• 思路：首先通过动态规划判断字符串 s 是否可以被拆分（类似单词拆分 I 的方法）。然后使用回溯法结合动态规划的结果，在可以拆分的基础上，遍历字典，尝试将每个单词添加到当前结果中，递归地构建所有可能的句子。

1. 最小路径和

• 题目描述：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。例如，grid = [[1,3,1],[1,5,1],[4,2,1]]，输出 7，因为路径 1→3→1→1→1 的总和最小。
• 思路：定义状态 dp[i][j] 表示到达位置 (i, j) 的最小路径和。dp[0][0] = grid[0][0]，对于 i > 0 且 j > 0，dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]，对于第一行 dp[0][j] = dp[0][j - 1] + grid[0][j]，对于第一列 dp[i][0] = dp[i - 1][0] + grid[i][0]。最后 dp[m - 1][n - 1] 即为所求的最小路径和。

1.3

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char const *argv[]) {
    int coins[] = {3, 5};
    int count = sizeof(coins) / sizeof(int);
    int amount = 8;

    int dp[amount + 1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = amount + 1;    // big number
        for (int c = 0; c < count; c++) {
            int coin = coins[c];
            if (i >= coin) {
                if (dp[i] > dp[i - coin] + 1) {
                    dp[i] = dp[i - coin] + 1;
                }
            }
        }
    }

    for (int i = 0; i <= amount; i++) {
        printf("%d,", dp[i]);
    }
    printf("\n");
    if (dp[amount] > amount || dp[amount] == 0) {
        printf("-1\n");
    } else {
        printf("%d\n", dp[amount]);
    }
    return 0;
}

1.4

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char const *argv[]) {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int count = sizeof(nums) / sizeof(int);
    int dp[count];
    dp[0] = nums[0];
    for (int i = 1; i < count; i++) {
        dp[i] = nums[i];
        if (dp[i - 1] > 0) {
            dp[i] += dp[i - 1];
        }
    }

    int max = dp[0];
    for (int i = 1; i < count; i++) {
        if (dp[i] > max) {
            max = dp[i];
        }
    }

    for (int i = 0; i < count; i++) {
        printf("%d,", dp[i]);
    }
    printf("\n");
    printf("%d\n", max);

    return 0;
}