标签： 动态规划

目标

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

说明：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

思路

返回将字符串划分为回文子串的所有可能方案。

定义 dp[i] 表示将前 i + 1 个字符划分为回文子串的所有可能方案。dp[i] 可以取 dp[i - 1] 每种方案的最后一或两个回文，判断能否与当前字符合并成新的回文。

代码

/**
 * @date 2025-03-01 20:16
 */
public class Partition131 {

    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>>[] dp = new List[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        char[] chars = s.toCharArray();
        dp[0].add(new ArrayList<>());
        dp[0].get(0).add((String.valueOf(chars[0])));
        for (int i = 1; i < n; i++) {
            dp[i] = new ArrayList<>();
            for (List<String> list : dp[i - 1]) {
                // 首先将单个字符加入
                List<String> tmp = new ArrayList<>(list);
                tmp.add(String.valueOf(chars[i]));
                dp[i].add(tmp);
                String cur = String.valueOf(chars[i]);
                // 判断能与最后一个回文合并成新的回文
                if (list.get(list.size() - 1).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 1));
                    tmp.add(list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
                // 判断能否与后两个回文合并成新的回文
                if (list.size() > 1 && list.get(list.size() - 2).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 2));
                    tmp.add(list.get(list.size() - 2) + list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
            }
        }
        return dp[n - 1];
    }

}

性能

时间复杂度 O(n * 2^n)，假设每个字符之间都有一个逗号，考虑选或不选共有 2^(n - 1) 种划分。前 i + 1 个 字符有 2^i 种划分， 等比数列求和得到 2^n - 1。

目标

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

说明：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

思路

有一个 m x n 的二进制矩阵，0 代表空位，1 代表有障碍物。有一个机器人可以向右或向下移动，求从 (0,0) 到 (m - 1, n - 1) 的路径有多少。

定义 dp[i][j] 表示到达坐标 (i - 1, j - 1) 的不同路径数。这样定义可以省去单独初始化第一行第一列。状态转移方程为 当 obstacleGrid[i][j] == 0 时, dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，初值为 dp[0][1] = 1，可以视为从 (-1, 0) 到 (0, 0) 的路径数量，如果 (0, 0) 有障碍物则为 0，否则为 1。

代码

/**
 * @date 2025-02-01 20:05
 */
public class UniquePathsWithObstacles63 {

     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 0){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

}

性能

目标

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

说明:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

思路

数组 nums 的元素表示可以向后跳跃的最大长度，求从 0 跳到 n - 1 所需的最小跳跃次数。

定义 dp[i] 表示到达下标 i 所需的最小跳跃次数，状态转移方程为 dp[i + k] = min(dp[i] + 1)，其中 k ∈ [1, nums[i]]。

代码

/**
 * @date 2024-03-07 17:14
 */
public class CanJumpII45 {

    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 0x3f3f3f);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && j <= i + nums[i]; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }

}

性能

目标

给你一个 下标从 1 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动：

• 如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i + 1] 的水果。

注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。

请你返回获得所有水果所需要的 最少 金币数。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：
用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。
免费获得第 3 个水果。
请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：
用 prices[0] = 1 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 1 个金币购买第 3 个水果，你可以免费获得第 4 个水果。
免费获得第 4 个水果。

示例 3：

输入：prices = [26,18,6,12,49,7,45,45]
输出：39
解释：
用 prices[0] = 26 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 6 个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。
免费获得第 4 个水果。
免费获得第 5 个水果。
用 prices[5] = 7 个金币购买第 6 个水果，你可以免费获得第 7 和 第 8 个水果。
免费获得第 7 个水果。
免费获得第 8 个水果。
请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

说明：

1 <= prices.length <= 1000
1 <= prices[i] <= 10^5

思路

有 n 个水果，其价格由 prices 表示，当我们以 prices[i] 枚金币购买了第 i + 1 个苹果时，我们可以免费获得下标 [i + 1, i + i + 1] 的 所有 个苹果（当然也可以购买以获得后面的奖励），求获得全部苹果所需的最少硬币。

最直接的想法是记忆化搜索。

代码

/**
 * @date 2025-01-24 9:07
 */
public class MinimumCoins2944 {

    public int minimumCoins(int[] prices) {
        int[] mem = new int[2 * prices.length + 3];
        Arrays.fill(mem, Integer.MAX_VALUE);
        return dfs(0, prices, mem, 0);
    }

    public int dfs(int index, int[] prices, int[] mem, int cost) {
        int n = prices.length;
        if (index >= n) {
            return cost;
        }
        int res = cost + prices[index];
        int next = index * 2 + 2;
        if (mem[next] == Integer.MAX_VALUE) {
            mem[next] = dfs(next, prices, mem, 0);
        }
        int remainder = mem[next];
        if (remainder == 0) {
            return res;
        }
        for (int i = index + 1; i < n && i <= index * 2 + 1; i++) {
            if (mem[i] == Integer.MAX_VALUE) {
                mem[i] = dfs(i, prices, mem, 0);
            }
            remainder = Math.min(mem[i], remainder);
        }
        return res + remainder;
    }

}

性能