动态规划

70. 爬楼梯

https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-100-liked

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

1 <= n <= 45

---

1. 动态规划

非常经典的动态规划

状态i当前在第i台阶

dp[i]表示爬到i的方法

dp[i] = dp[i-1]+dp[i-2].

从左到右填表

显然可以滚动优化

使用dp_i,dp_im1,dp_im2

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int dp_im2 = 1; // 代表 dp[i-2]
        int dp_im1 = 2; // 代表 dp[i-1]
        int dp_i = 0;
        for (int i = 3; i <= n; i++) {
            dp_i = dp_im1 + dp_im2;
            //注意更新顺序，先更新i-2,在更新i-1,防止i-1被覆盖

            dp_im2 = dp_im1;
            dp_im1 = dp_i;
        }
        return dp_i; 
    }
}

2. 下面是记忆化搜索

缓存：我们使用一个数组，通常称为 memo，来存储已经计算过的子问题的解。

在每次递归计算前，先检查 memo 中是否已有答案。如果有，直接返回答案，避免重复计算。

import java.util.Arrays;

class Solution {
    // memo 数组用于存储 f(i) 的计算结果，-1 表示尚未计算
    int[] memo;

    public int climbStairs(int n) {
        // 初始化 memo 数组，大小为 n+1，因为我们需要存储 f(1) 到 f(n) 的结果
        memo = new int[n + 1];
        // 使用一个特殊值（如 -1）来标记尚未计算的状态
        Arrays.fill(memo, -1);
        
        return solve(n);
    }

    /**
     * 递归函数，计算爬到第 n 阶的方法数
     * @param n 当前的目标台阶
     * @return 到达第 n 阶的方法数
     */
    private int solve(int n) {
        // 1. 基本情况（递归的终止条件）
        if (n <= 1) {
            return 1; // 到达第0阶有1种方法（不动），到达第1阶有1种方法
        }
        if (n == 2) {
            return 2; // 到达第2阶有2种方法
        }

        // 2. 检查缓存中是否已有结果
        // 如果 memo[n] 不是初始值 -1，说明 solve(n) 已经被计算过，直接返回结果
        if (memo[n] != -1) {
            return memo[n];
        }

        // 3. 递归计算，并将结果存入缓存
        // 如果没有缓存，则进行递归计算
        // 状态转移方程：f(n) = f(n-1) + f(n-2)
        int result = solve(n - 1) + solve(n - 2);
        
        // 将计算结果存入 memo 数组，以便下次使用
        memo[n] = result;

        // 4. 返回结果
        return result;
    }
}

3. 矩阵快速幂

整个过程分为三个核心步骤：

1. 构建状态转移矩阵：将递推关系 f(n) = f(n-1) + f(n-2) 转化为矩阵乘法的形式。
2. 应用快速幂：高效地计算这个矩阵的 N 次幂。
3. 求解最终结果：用计算出的矩阵乘以初始状态，得到最终答案。

---

第一步：构建状态转移矩阵

我们的目标是找到一个矩阵 M，它能将状态从 n-1 推进到 n。

一个“状态”通常包含递推关系中需要的所有前置项。对于 f(n) = f(n-1) + f(n-2)，我们需要 f(n-1) 和 f(n-2) 来计算 f(n)。因此，我们可以定义一个状态向量：

[ f(n)   ]
[ f(n-1) ]

我们希望找到一个 2x2 的矩阵 M，使得：

[ f(n)   ]   [ ?  ? ]   [ f(n-1) ]
[        ] = [      ] * [        ]
[ f(n-1) ]   [ ?  ? ]   [ f(n-2) ]

我们来填充这个矩阵 M：

1. 第一行：根据递推公式 f(n) = 1 * f(n-1) + 1 * f(n-2)。这告诉我们矩阵的第一行应该是 [1, 1]。

   f(n) = [1, 1] * [ f(n-1) ]
                   [ f(n-2) ]

2. 第二行：我们需要得到 f(n-1)。这是一个简单的恒等式：f(n-1) = 1 * f(n-1) + 0 * f(n-2)。这告诉我们矩阵的第二行应该是 [1, 0]。

   f(n-1) = [1, 0] * [ f(n-1) ]
                     [ f(n-2) ]

将它们组合起来，我们就得到了状态转移矩阵 M:

[ f(n)   ]   [ 1  1 ]   [ f(n-1) ]
[        ] = [      ] * [        ]
[ f(n-1) ]   [ 1  0 ]   [ f(n-2) ]

这个矩阵 M = [[1, 1], [1, 0]] 就是我们需要的魔法钥匙。它能将状态从 (n-1, n-2) 推进到 (n, n-1)。

---

第二步：应用快速幂

通过反复应用这个矩阵，我们可以从初始状态跳跃到任意的 n 状态。

[ f(3), f(2) ]^T = M * [ f(2), f(1) ]^T
[ f(4), f(3) ]^T = M * [ f(3), f(2) ]^T = M * (M * [ f(2), f(1) ]^T) = M^2 * [ f(2), f(1) ]^T

以此类推，我们可以得到通用公式：

[ f(n), f(n-1) ]^T = M^(n-2) * [ f(2), f(1) ]^T

• 注意：这里的幂是 n-2，因为我们是从 f(2) 和 f(1) 的状态开始跳跃 n-2 次到达 f(n) 的状态。

现在问题变成了如何快速计算 M^(n-2)。如果一次一次地乘，复杂度还是 O(n)。这里就要用到快速幂算法（也叫二进制取幂）。

它的核心思想是：

• 如果 k 是偶数，A^k = (A^(k/2))^2
• 如果 k 是奇数，A^k = A * A^(k-1)

通过这种方式，我们可以将计算 M^k 的时间复杂度从 O(k) 降到 O(log k)。

---

第三步：求解最终结果

在爬楼梯问题中，我们的初始状态是：

• f(1) = 1
• f(2) = 2

所以我们的初始状态向量是 [f(2), f(1)]^T = [2, 1]^T。

求解 climbStairs(n) 的完整流程：

1. 处理边界情况 n <= 2。
2. 定义转移矩阵 M = [[1, 1], [1, 0]]。
3. 使用快速幂算法计算 M_result = M^(n-2)。
4. 将结果矩阵与初始向量相乘：

   [ f(n)   ]   [ M_result[0][0]  M_result[0][1] ]   [ 2 ]
   [        ] = [                                ] * [   ]
   [ f(n-1) ]   [ M_result[1][0]  M_result[1][1] ]   [ 1 ]

5. 我们需要的答案 f(n) 就是结果向量的第一个元素：
   f(n) = M_result[0][0] * 2 + M_result[0][1] * 1

示例：计算 climbStairs(4)

1. n=4，我们需要计算 M^(4-2) = M^2。
2. M = [[1, 1], [1, 0]]
3. M^2 = M * M = [[1, 1], [1, 0]] * [[1, 1], [1, 0]] = [[2, 1], [1, 1]]
4. 用 M^2 乘以初始向量 [2, 1]^T：

   [ f(4) ]   [ 2  1 ]   [ 2 ]   [ 2*2 + 1*1 ]   [ 5 ]
   [      ] = [      ] * [   ] = [             ] = [   ]
   [ f(3) ]   [ 1  1 ]   [ 1 ]   [ 1*2 + 1*1 ]   [ 3 ]

5. 最终结果 f(4) = 5，与我们手动计算的结果一致。

Java 代码实现

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        // 状态转移矩阵
        long[][] M = {{1, 1}, {1, 0}};

        // 使用快速幂计算 M 的 n-2 次方
        long[][] M_pow_n_minus_2 = matrixPow(M, n - 2);

        // 最终结果 f(n) = M_pow[0][0] * f(2) + M_pow[0][1] * f(1)
        // f(2) = 2, f(1) = 1
        long result = M_pow_n_minus_2[0][0] * 2 + M_pow_n_minus_2[0][1] * 1;
        
        return (int) result;
    }

    // 矩阵快速幂
    private long[][] matrixPow(long[][] base, int exp) {
        // 结果矩阵初始化为单位矩阵
        long[][] result = {{1, 0}, {0, 1}};
        while (exp > 0) {
            // 如果指数是奇数，结果矩阵乘以当前的 base 矩阵
            if ((exp & 1) == 1) {
                result = multiply(result, base);
            }
            // base 矩阵自乘
            base = multiply(base, base);
            // 指数右移一位（相当于除以2）
            exp >>= 1;
        }
        return result;
    }

    // 2x2 矩阵乘法
    private long[][] multiply(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
        c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
        c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
        c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
        return c;
    }
}

• 时间复杂度：O(log n)。矩阵乘法是常数时间（因为矩阵大小固定），快速幂循环 log n 次。
• 空间复杂度：O(1)。只使用了几个固定大小的矩阵变量。

118. 杨辉三角

https://leetcode.cn/problems/pascals-triangle/description/?envType=study-plan-v2&envId=top-100-liked

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

---

状态定义为(m,n),第m行n个

dp[m][n] = dp[m-1][n-1] + dp[m-1][n]

从上往下，从左往右填表

dp[m][0] = 1,dp[m][n] = 1;

n <= m

耗费时间O(mn/2)=O(mn)

空间O(mn)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        int[][] dp = new int[numRows][numRows];
        for (int m = 0; m < numRows; m++) {
            dp[m][0] = 1;
            dp[m][m] = 1;
        }
        for (int m = 1; m < numRows; m++) {
            for (int n = 1; n < m ; n++) {
                dp[m][n] = dp[m-1][n-1] + dp[m-1][n];
            }
        }
        for (int m = 0; m < numRows; m++) {
            List<Integer> row = new ArrayList<>();
            for (int n = 0; n <= m; n++) {
                row.add(dp[m][n]);
            }
            result.add(new ArrayList<>(row));
        }
        return result;
    }
}

更好的实现可以直接不适用dp数组

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> firstRow = new ArrayList<>();
        result.add(firstRow);
        result.get(0).add(1);
        
        for (int m = 1; m < numRows; m++) {
            List<Integer> curRow = new ArrayList<>();
            List<Integer> preRow = result.get(m-1);
            curRow.add(1);
            for (int n = 1; n < m; n++) {
                int sum = preRow.get(n-1) + preRow.get(n);
                curRow.add(sum);
            }
            curRow.add(1);
            result.add(curRow);
        }
        return result;
    }
}

额外空间降为O(numRow)

198. 打家劫舍

https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-liked

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

---

状态为i，代表有i个屋子

dp[i]表示这i个屋子最大偷窃利润

dp[i] = MAX(dp[i-2]+nums[i],dp[i-1])(对于dp[i-1],不必关心到底偷了i-1没有，如果没偷就等于dp[i-2],状态转移方程依然满足；偷了更加满足)

边界：dp[0] = nums[0],dp[1] = MAX(nums[0],nums[1])

时空O(n)

class Solution {
    public int rob(int[] nums) {
        if (nums.length <= 1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-2] + nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

事实上我们只关心dp[i],dp[i-1],dp[i-2]

滚动优化

class Solution {
    public int rob(int[] nums) {
        if (nums.length <= 1){
            return nums[0];
        }
        int dp_i = Math.max(nums[0],nums[1]);
        int dp_im2 = nums[0];
        int dp_im1 = Math.max(nums[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp_i = Math.max(dp_im2 + nums[i],dp_im1);
            dp_im2 = dp_im1;
            dp_im1 = dp_i;
        }
        return dp_i;
    }
}

空间O(1)

2. 记忆化搜索

递归

定义一个solve(i)函数，表示从i间屋子开始直到末尾打劫获得的最大收益

也分成两个情况

偷i，利润是nums[i] + solve(i+2)

不偷i，利润solve(i+1).

取最大值。

但这样会有很多重复。比如，solve(5)会被solve(0),solve(1),solve(2)等等各调用一次。使用memo记忆化

import java.util.Arrays;

class Solution {
    int[] memo;

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        memo = new int[nums.length];
        Arrays.fill(memo,-1);
        return solve(0, nums);
    }

    private int solve(int i, int[] nums) {
        if(i >= nums.length){
            return 0;
        }
        if (memo[i] != -1){
            return memo[i];
        }
        int result = Math.max(solve(i+1,nums),nums[i] + solve(i+2,nums));
        memo[i] = result;
        return result;
    }
}

279. 完全平方数

https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

---

1. 动态规划

如果一个数 n 可以由多个完全平方数相加得到，那么它一定可以表示为 n = k + ii，其中 ii 是一个完全平方数，而 k 是 n - i*i 的结果。

为了使组成 n 的完全平方数的数量最少，我们需要让组成 k 也就是n-i*i的完全平方数的数量也最少。

状态i，表示求和为i的最少完全平方数个数

因此得到状态转移方程

dp[i] = min(dp[i-jj]+1,j从1到jj恰好小于等于i)（j从0开始没意义，如果是0的话还是dp[i]自己无法计算会卡壳）

时间复杂度：1+sqrt(2)+……根号n。

这个级数小于等于n*sqrt(n)(都放缩到最后一项)

大于等于n*sqrt(n)(丢弃前半项，从sqrt(n/2)保留)

因此时间复杂度是O(n*sqrt(n)),算出来大概是10^6，可以接受

空间O(n)

import java.util.Arrays;

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;//这里我们要认为是0，后边的话计算4 = 4+0认为是一个，0不计入
        Arrays.fill(dp,1,dp.length,Integer.MAX_VALUE);//包头不包尾
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*j <= i; j++) {
                dp[i] =Math.min(dp[i-j*j]+1,dp[i]);
            }
        }
        return dp[n];
    }
}

2. BFS

把每个数看成一个节点（从0到n)

如果任意两个数可以满足A - i*i = B，那么AB之间就有边

问题转化为，求从n到0的最短路径

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int numSquares(int n) {
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        int levelSize = 0;
        visited[n] = true;
        queue.offer(n);
        while (!queue.isEmpty()){
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                int curNode = queue.poll();
                for (int j = 1; j*j <= curNode; j++) {
                    int nextNode = curNode - j*j;
                    if (nextNode == 0){
                        return levelSize+1;
                    }
                    if (!visited[nextNode]){
                        queue.add(nextNode);
                        visited[nextNode] = true;//加入时进行标记，可以防止重复入队
                    }
                }
            }
            levelSize++;
        }
        return levelSize;
    }
}

空间复杂度:O(V+E) ,V = n+1,E = sqrt(n)+……sqrt(1) = nsqre(n), O(nsqrt(n))

空间O(n)

322. 零钱兑换

https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

---

状态i

i代表要凑成的金额

dp[i]表示凑成i最少硬币数目

dp[i] = MIN(dp[i-j],j从coins[0]到coins[length-1]并且可以是k倍的 (保证i-j>=0))

dp[0] = 0

从左向右填表

时间O(length*amount)可以接受

空间O(amount)

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < coins.length ; j++) {
                if (coins[j] > i||dp[i-coins[j]] == Integer.MAX_VALUE){//如果硬币值比i还大，或者需要的子问题无解，跳过
                    continue;
                }

                dp[i] = Math.min(dp[i-coins[j]]+1,dp[i]);
            }
        }
        return dp[dp.length-1] == Integer.MAX_VALUE ? -1 : dp[dp.length-1];
    }
}

2. BFS

属于“求固定成本操作下的最少次数”

把每个数看成节点，

对于节点A，如果存在硬币使得A-value = B，那么AB存在一条边

实际上就是找从A出发到0的最短路径

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0){
            return 0;
        }
        int levelSize = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(amount);
        boolean[] visited = new boolean[amount+1];
        visited[amount] = true;
        
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curNode = queue.poll();
                for (int num : coins) {
                    int nextNode = curNode - num;
                    if (nextNode == 0){
                        return levelSize+1;
                    }
                    if (nextNode < 0){
                        continue;
                    }
                    if (!visited[nextNode]){
                        queue.add(nextNode);
                        visited[nextNode] = true;
                    }
                }
            }
            levelSize++;
        }
        return -1;//只有在队列为空并且没有访问过0才可能执行到这里，因此不必判断直接返回-1
    }
}

时间:O(V+E),O(V) = O(n),O(E) = O(coins.length * n),复杂度还是O(coins.length * amount)

空间:O(amount)

3. 记忆化搜索

定义solve(i),表示返回凑出金额i的最小硬币数目

结果就是MIN(solve(i-n)+1),n是coins里面的数

例1中，solve(11)会调用solve(9),solve(10)也调用solve(9),有重复采取记忆搜索

import java.util.Arrays;
import java.util.Map;

class Solution {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        memo[0] = 0;
        return solve(coins, amount);
    }

    private int solve(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (memo[amount] != Integer.MAX_VALUE) {
            return memo[amount];
        }
        for (int num : coins) {
            if (amount - num < 0) {
                continue;
            }
            int sum = solve(coins, amount - num) ;
            if (sum == -1) {
                continue;
            }
            memo[amount] = Math.min(memo[amount],sum+1);
        }
        if (memo[amount] == Integer.MAX_VALUE){
            memo[amount] = -1;
        }
        return memo[amount];
    }
}

时间:每次调用本地耗费O(length),主调用O(amount)次，复杂度还是O(length*amount)(部分节点重复调用耗费O(1),这部分副调用消耗可以认为是隶属的循坏外面的那次大的调用的一部分)

空间:缓存O(amount),调用栈O(amount)，总共O(amount)

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。

如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

---

1. 动态规划

定义状态dp[i] 表示[0,i-1]的字符串能否被匹配（这里取的是前i个，如果定义成[0,i]会非常麻烦。dp[0] 的真假需要额外判断，dp[i]都有两种情况，一种是s[0,i]本身是单词，一种是存在分割点）

dp[i] = OR(dp[j] && wordDict.has(s.subString(j+1,i+1))),j从0开始循环到i-1

dp[0] = true

使用哈希集合储存wordDict

时间复杂度：O(1+2+……+n-1) = O(n^2)

空间O(n)

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j]){
                    if (set.contains(s.substring(j,i))){
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[s.length()];
    }
}

实际上这个实现时间复杂度是O(N^3).内部循环子串复杂度O(i-j),哈希复杂度（计算hashcode)O(i-j),总体还是O(i-j).

外层循环n次，内层循环平均n次，最内侧判断最差n，因此是O(n^3)

事实上有很多判断是不必要的。只有i-j和字典中某个单词长度相等时，才可能作为答案

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (String string : wordDict){
                int len = string.length();
                if (i >= len && dp[i - len] && s.substring(i - len, i).equals(string)){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

时间:O(nml),n时单词长度，m是词典单词个数，l是单词平均长度，复杂度显著下降
2. 记忆化

1. 定义一个函数 dfs(startIndex)，表示从 s 的 startIndex 开始的子字符串是否可以被成功拆分。
2. 在该函数中，遍历所有字典单词，检查是否有单词能作为 s[startIndex...] 的前缀。
3. 如果找到了一个匹配的单词 word，就递归调用 dfs(startIndex + word.length())。如果递归调用返回 true，那么说明从 startIndex 开始的拆分是可行的，当前函数也返回 true。
4. 如果遍历完所有单词都无法成功拆分，则返回 false。
5. 记忆化：为了避免对同一个 startIndex 进行重复计算（这会导致指数级的时间复杂度），我们使用一个数组或哈希表 memo 来记录已经计算过的结果。在 dfs 函数开头，先检查 memo[startIndex] 是否已经有结果，如果有，直接返回。在函数返回前，将计算结果存入 memo。

import java.util.Arrays;
import java.util.List;
import java.util.Set;

class Solution {
    int[] memo;

    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length() + 1];
        Arrays.fill(memo,-1);
        return solve(s,wordDict,0);
    }

    private boolean solve(String s, List<String> wordDict, int startIndex) {
        if (startIndex == s.length()) {
            return true;
        }
        if (startIndex > s.length()){
            return false;
        }
        if (memo[startIndex] != -1) {
            return memo[startIndex] == 1;
        }
        
        for (String string : wordDict) {
            if (startIndex + string.length() > s.length()){
                continue;
            }
            if (string.equals(s.substring(startIndex,startIndex+string.length()))) {
                if (solve(s, wordDict, startIndex + string.length())) {
                    memo[startIndex] = 1;
                    return true;
                }
            }
        }
        memo[startIndex] = 0;
        return false;
    }
}

时间O(nml),空间O(n)