算法 4（动态规划）

/* 回溯 */
void backtrack(List<Integer> choices, int state, int n, List<Integer> res) {
    // 当爬到第 n 阶时，方案数量加 1
    if (state == n)
        res.set(0, res.get(0) + 1);
    // 遍历所有选择
    for (Integer choice : choices) {
        // 剪枝：不允许越过第 n 阶
        if (state + choice > n)
            continue;
        // 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res);
        // 回退
    }
}

/* 爬楼梯：回溯 */
int climbingStairsBacktrack(int n) {
    List<Integer> choices = Arrays.asList(1, 2); // 可选择向上爬 1 阶或 2 阶
    int state = 0; // 从第 0 阶开始爬
    List<Integer> res = new ArrayList<>();
    res.add(0); // 使用 res[0] 记录方案数量
    backtrack(choices, state, n, res);
    return res.get(0);
}

/* 搜索 */
int dfs(int i) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1) + dfs(i - 2);
    return count;
}

/* 爬楼梯：搜索 */
int climbStairsDFS(int n) {
    return dfs(n);
}

/* 记忆化搜索 */
int dfs(int i, int[] mem) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2) return i;
    // 若存在记录 dp[i] ，则直接返回之
    if (mem[i] != -1) return mem[i];
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1, mem) + dfs(i - 2, mem);
    // 记录 dp[i]
    mem[i] = count;
    return count;
}

/* 爬楼梯：记忆化搜索 */
int climbStairsDFSMem(int n) {
    // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    int[] mem = new int[n + 1];
    Arrays.fill(mem, -1);
    return dfs(n, mem);
}

/* 爬楼梯：动态规划 */
int climbStairsDP(int n) {
    // 【定义dp表】用于存储子问题的解（这里用 n+2 是为了避免 n=1 时数组 dp 不存在dp[2]报错）
    int[] dp = new int[n + 2];
    // 【边界条件】预设最小子问题的解
    dp[1] = 1;
    dp[2] = 2;
    // 【遍历顺序】从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

/* 爬楼梯：空间优化后的动态规划 */
int climbStairsDPComp(int n) {
    if (n == 1 || n == 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}

/* 爬楼梯最小代价：动态规划 */
int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    // 【初始化 dp 表】用于存储子问题的解
    int[] dp = new int[n + 1];
    // 【边界条件】预设最小子问题的解
    dp[0] = dp[1] = 0;
    // 【状态转移】从较小子问题逐步求解较大子问题
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i-1], dp[i - 2] + cost[i-2]);
    }
    return dp[n];
}

/* 带约束爬楼梯：动态规划 */
int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 【初始化 dp 表】
    int[][] dp = new int[n + 1][3];
    // 【初始状态】预设最小子问题的解
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1;
    // 【状态转移】从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    }
    return dp[n][1] + dp[n][2];
}

/* 最小路径和：暴力搜索 */
int minPathSumDFS(int[][] grid, int i, int j) {
    // 【Base Case】若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 【剪枝】若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // 【递归】计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // 【状态转移方程】返回从左上角到 (i, j) 的最小路径代价
    return Math.min(left, up) + grid[i][j];
}

/* 最小路径和：记忆化搜索 */
int minPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
    // 【Base Case】若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 【剪枝】若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // 【记忆化搜索】若已有记录，则直接返回
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // 【递归】左边和上边单元格的最小路径代价
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // 【状态转移方程】记录并返回左上角到 (i, j) 的最小路径代价
    mem[i][j] = Math.min(left, up) + grid[i][j];
    return mem[i][j];
}

/* 最小路径和：动态规划 */
int minPathSumDP(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // 【定义dp表】
    int[][] dp = new int[n][m];
    dp[0][0] = grid[0][0];
    // 【边界条件】首行
    for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    // 【边界条件】首列
    for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    // 【遍历顺序】其余行和列
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}

/* 最小路径和：空间优化后的动态规划 */
int minPathSumDPComp(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // 【定义dp表】
    int[] dp = new int[m];
    // 【边界条件】首行
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 【遍历顺序】其余行
    for (int i = 1; i < n; i++) {
        // 【边界条件】首列
        dp[0] = dp[0] + grid[i][0];
        // 其余列
        for (int j = 1; j < m; j++) {
            // 【状态转移方程】
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}

public int uniquePaths(int m, int n) {
    int[][] f = new int[m][n];
    for (int i = 0; i < m; ++i) f[i][0] = 1;
    for (int j = 0; j < n; ++j) f[0][j] = 1;
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}

public int uniquePaths(int m, int n) {
    int[] f = new int[n];
    for (int i = 0; i < n; ++i) f[i] = 1;
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            f[j] += f[j - 1];
        }
    }
    return f[n - 1];
}

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res = new ArrayList<>();
    int[][] matrix = new int[numRows][numRows];
    for (int i = 0; i < numRows; i++) {
        matrix[i][0] = 1;
        matrix[i][i] = 1;
        for (int j = 1; j < i; j++)
            matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - 1];
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j <= i; j++)
            list.add(matrix[i][j]);
        res.add(list);
    }
    return res;
}

/* 0-1 背包：暴力搜索 */
int knapsackDFS(int[] wgt, int[] val, int i, int c) {
    // 【Base Case】若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) return 0;
    // 【剪枝】若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) return knapsackDFS(wgt, val, i - 1, c);
    // 【递归】计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 【状态转移方程】返回两种方案中价值更大的那一个
    return Math.max(no, yes);
}

/* 0-1 背包：记忆化搜索 */
int knapsackDFSMem(int[] wgt, int[] val, int[][] mem, int i, int c) {
    // 【Base Case】若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) return 0;
    // 【记忆化搜索】若已有记录，则直接返回
    if (mem[i][c] != -1) return mem[i][c];
    // 【剪枝】若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) return knapsackDFSMem(wgt, val, mem, i - 1, c);
    // 【递归】计算不放入和放入物品 i 的最大价值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 【状态转移方程】记录并返回两种方案中价值更大的那一个
    mem[i][c] = Math.max(no, yes);
    return mem[i][c];
}

/* 0-1 背包：动态规划 */
int knapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 【初始化 dp 表】
    int[][] dp = new int[n + 1][cap + 1];
    // 【边界条件】第一行和第一列默认为0
    // 【遍历顺序】
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            // 【剪枝】若超过背包容量，则不选物品 i
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];
            // 【状态转移方程】不选和选物品 i 这两种方案的较大值
            else dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[n][cap];
}

/* 0-1 背包：空间优化后的动态规划 */
int knapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 【定义dp表】
    int[] dp = new int[cap + 1];
    // 【遍历顺序】
    for (int i = 1; i <= n; i++) {
        // 对应背包的一维dp数组倒序遍历
        for (int c = cap; c >= 1; c--) {
            // 【剪枝】若超过背包容量，则保持不变
            if (wgt[i - 1] > c) continue;
            // 【状态转移方程】
            else dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[cap];
}

boolean canPartition(int[] nums) {
    // 【定义dp数组】
    // 第一维与物品下标定义一致，从 0 开始到 nums.length-1，下标 0 也对应一个物品；
    // 第二维与背包容量定义一致，从 0 到 sum/2
    int len = nums.length;
    int sum = 0;
    for (int num : nums) sum += num;
    // 特判：如果是奇数，就不符合要求
    if ((sum %2 ) != 0) return false;
    int target = sum / 2; // 目标背包容量
    boolean[][] dp = new boolean[len][target + 1];
    // 【边界条件】第一维数组下标为0，只有一个数，只有当背包容积=该数的值时才能恰好装满，子问题解为 true
    if (nums[0] <= target) dp[0][nums[0]] = true;
    // 这里本身没有意义，是为了确保 i=1 且 j=nums[i] 时，dp[1][nums[i]]=dp[0][0]=true，进而后续 i=2/3/... 且 j=nums[i] 时，dp[i][nums[i]]=dp[i-1][0]
    dp[0][0] = true;
    // 【遍历顺序】再填表格后面几行
    for (int i = 1; i < len; i++) {
        for (int j = 1; j <= target; j++) {
            // 【状态转移方程】
            if(j < nums[i]) dp[i][j] = dp[i-1][j];
            // dp[i - 1][j]表示该物品不放入背包，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
            // dp[i - 1][j - nums[i]]表示该物品放入背包。如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]
            else dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
        }
    }
    return dp[len - 1][target];
}

boolean canPartition(int[] nums) {
    // 【定义dp数组】dp[j] 表示：是否能凑出和为 j
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果是奇数，无法平分
    if ((sum % 2) != 0) return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    // 【初始化】第一行两个值
    if (nums[0] <= target) dp[nums[0]] = true;
    dp[0] = true;
    // 【遍历顺序】
    // 外层：遍历物品（数组中的每个数字）
    for (int i = 1; i < nums.length; i++) {
        // 内层：倒序遍历背包容量
        for (int j = target; j >= 1; j--) {
            // 【状态转移方程】
            if(j < nums[i]) dp[j] = dp[j];
            else dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
}

int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int num : nums) sum += num;
    // 特判：如果目标和的绝对值大于总和，无法达成
    if (Math.abs(target) > sum) return 0;
    // 特判：如果 (sum + target) 是奇数，无法算出整数的 pos
    if ((sum + target) % 2 != 0) return 0;
    // 【定义dp数组】
    int pos = (sum + target) / 2; // 目标背包容量
    // 第一维与物品下标定义一致，从 0 到 nums.length-1；
    // 第二维与背包容量定义一致，从 0 到 pos
    int[][] dp = new int[nums.length][pos + 1];
    // 【边界条件：处理第一列 dp[i][0]】前 i+1 个数凑出和为 0 的方法数
    // 只要前面的数字里有 0，那么 0 可以取 +0 或 -0，方案数就会翻倍
    int numZeros = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) numZeros++;
        // 2的numZeros次方：每个0都有两种选择（+或-），非0数都不选（只有1种）
        dp[i][0] = (int) Math.pow(2, numZeros);
    }
    // 【边界条件：处理第一行 dp[0][j]】只有一个数 nums[0] 时，只有当背包容量等于该数值时，才有一种方法（选它）
    if (nums[0] != 0 && nums[0] <= pos) dp[0][nums[0]] = 1;
    // 注意：dp[0][0] 已经在上面的第一列循环中被初始化，无需重复赋值
    // 【遍历顺序】
    for (int i = 1; i < nums.length; i++) {
        for (int j = 1; j <= pos; j++) {
            // 【状态转移方程】
            // 当前物品太重，装不下，方法数继承自上一行（不选该物品）
            if (j < nums[i]) dp[i][j] = dp[i - 1][j];
            // 能装下，方法数 = (不选该物品的方法数) + (选该物品的方法数)
            // dp[i-1][j]：不选 nums[i]，看前 i-1 个物品凑成 j 的方法
            // dp[i-1][j-nums[i]]：选 nums[i]，看前 i-1 个物品凑成 j-nums[i] 的方法
            else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
        }
    }
    return dp[nums.length - 1][pos];
}

int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int i = 0; i < nums.length; i++) sum += nums[i];
    // 特判：如果目标和的绝对值大于总和，无法达成
    if (Math.abs(target) > sum) return 0;
    // 特判：如果 (target + sum) 是奇数，无法算出整数的 pos，无解
    if ((target + sum) % 2 == 1) return 0;

    int pos = (target + sum) / 2;
    // 【定义dp数组】dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法
    int[] dp = new int[pos + 1];

    // 【边界条件】dp[0] = 1 表示装满容量为 0 的背包，有 1 种方法（即什么都不选）
    // ⚠️注意：这里不需要像二维数组那样处理 0 的幂次，因为一维递推会自动处理累加
    dp[0] = 1;
    // 【遍历顺序】
    // 外层：遍历物品（数组中的每个数字）
    for (int i = 0; i < nums.length; i++) {
        // 内层：倒序遍历背包容量（01背包）
        // ⚠️注意：这里减到0结束，之前则是从1开始
        for (int j = pos; j >= 0; j--) {
            // 【状态转移方程】
            if(j < nums[i]) continue;
            // dp[j]（等号右边）：不选当前物品 nums[i]，继承之前的方法数
            // dp[j - nums[i]]：选当前物品 nums[i]，加上凑成剩余容量的方法数
            // 两者相加即为当前总方法数
            else dp[j] += dp[j - nums[i]];
        }
    }
    return dp[pos];
}

/* 完全背包：动态规划 */
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 【定义dp表】
    int[][] dp = new int[n + 1][cap + 1];
    // 【遍历顺序】
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            // 【剪枝】若超过背包容量，则不选物品 i
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];
            // 【状态转移方程】不选和选物品 i 这两种方案的较大值
            else dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[n][cap];
}

/* 完全背包：空间优化后的动态规划 */
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 【定义dp表】
    int[] dp = new int[cap + 1];
    // 【遍历顺序】
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            // 【剪枝】
            if (wgt[i - 1] >= c) continue;
            // 【状态转移方程】
            else dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[cap];
}

/* 零钱兑换：动态规划 */
int coinChangeDP(int[] coins, int amt) {
    int n = coins.length;
    int MAX = amt + 1;
    // 【定义dp表】
    int[][] dp = new int[n + 1][amt + 1];
    // 【边界条件】首行首列
    for (int a = 1; a <= amt; a++) {
        dp[0][a] = MAX;
    }
    // 【遍历顺序】其余行和列
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            // 【剪枝】若超过目标金额，则不选硬币 i
            if (coins[i - 1] > a) dp[i][a] = dp[i - 1][a];
            // 【状态转移方程】不选和选硬币 i 这两种方案的较小值
            else dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
        }
    }
    return dp[n][amt] != MAX ? dp[n][amt] : -1;
}

/* 零钱兑换：空间优化后的动态规划 */
int coinChangeDPComp(int[] coins, int amt) {
    int n = coins.length;
    int MAX = amt + 1;
    // 【定义dp表】
    int[] dp = new int[amt + 1];
    // 【边界条件】
    Arrays.fill(dp, MAX);
    dp[0] = 0;
    // 【遍历顺序】
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            // 【剪枝】若超过目标金额，则不选硬币 i
            if (coins[i - 1] > a) dp[a] = dp[a];
            // 【状态转移方程】
            else dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}

/* 零钱兑换 II：动态规划 */
int coinChangeIIDP(int[] coins, int amt) {
    int n = coins.length;
    // 【定义dp表】
    int[][] dp = new int[n + 1][amt + 1];
    // 【边界条件】初始化首列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 【遍历顺序】
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            // 【剪枝】若超过目标金额，则不选硬币 i
            if (coins[i - 1] > a) dp[i][a] = dp[i - 1][a];
            // 【状态转移方程】不选和选硬币 i 这两种方案之和
            else dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

/* 零钱兑换 II：空间优化后的动态规划 */
int coinChangeIIDPComp(int[] coins, int amt) {
    int n = coins.length;
    // 【定义dp表】
    int[] dp = new int[amt + 1];
    // 【边界条件】
    dp[0] = 1;
    // 【遍历顺序】
    for (int i = 1; i <= n; i++) {
        // 不选和选硬币 i 这两种方案之和
        for (int a = 1; a <= amt; a++) {
            // 【剪枝】若超过目标金额，则不选硬币 i
            if (coins[i - 1] > a) dp[a] = dp[a];
            // 【状态转移方程】
            else dp[a] = dp[a] + dp[a - coins[i - 1]];
            }
        }
    }
    return dp[amt];
}

int combinationSum(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 0; i <= target; i++) {
        for (int j = 0; j < nums.length; j++) {
            // 【状态转移方程】
            if (i >= nums[j]) dp[i] += dp[i - nums[j]];
        }
    }
    return dp[target];
}

int numSquares(int n) {
    // 【定义dp表】dp[i]表示组成整数i所需的最少完全平方数个数
    int[] dp = new int[n + 1];
    // 【边界条件】
    // dp[0] = 0 已经在数组创建时默认初始化
    // 其他位置初始化为最坏情况：全部用1相加，即i个
    for (int i = 1; i <= n; i++) {
        dp[i] = i;
    }
    // 【遍历顺序】外层遍历物品
    // 这里的物品是 1*1, 2*2, 3*3 ... 直到 sqrt(n)
    for (int j = 1; j * j <= n; j++) {
        // 内层正序遍历背包容量（金额）
        for (int i = j*j; i <= n; i++) {
            // 【状态转移方程】
            dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
        }
    }
    return dp[n];
}

public boolean wordBreak(String s, List<String> wordDict) {
    // 将 List 转换为 HashSet，实现 O(1) 的快速查找
    Set<String> wordSet = new HashSet<>(wordDict);
    // 【定义dp数组】dp[i] 表示字符串 s 的前 i 个字符（即 s.substring(0, i)）能否被拆分
    boolean[] dp = new boolean[s.length() + 1];
    // 【边界条件】空字符串默认为 true，这是递推的基础
    dp[0] = true;
    //【遍历顺序】外层循环：遍历背包（字符串长度，从 1 到 s.length()）
    for (int i = 1; i <= s.length(); i++) {
        // 内层循环：遍历物品（分割点，从 0 到 i-1）
        for (int j = 0; j < i; j++) {
            // 截取子串：从下标 j 开始，长度为 i-j
            String word = s.substring(j, i);
            // 【状态转移方程】如果 s[0...j-1] 可以拆分（dp[j] 为 true）并且子串 s[j...i-1] 在字典里，那么 s[0...i-1] 就可以拆分
            if (wordSet.contains(word) && dp[j]) {
                dp[i] = true;
                break; // 既然已经确定可以拆分，就不需要继续尝试其他分割点了
            }
        }
    }
    return dp[s.length()];
}