LeetCode 热题 100-动态规划

LeetCode 热题 100-动态规划

爬楼梯

动态规划

f(n) = f(n-1) + f(n-2)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        int f0 = 1;
        int f1 = 1;
        for (int i = 2; i <= n; i++) {
            int f2 = f0 + f1;
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
}
JAVA
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

思考题

  1. 如果每次可以爬 1 或 2 或 3 个台阶呢？空间优化的写法要怎么做？
    • 定义三个变量：f0 = 1, f1 = 1, f2 = 2；
    • 从i=3开始计算，f3 = f0 + f1 + f2。
  2. 如果某些台阶不能爬呢？（输入一个数组表示不能爬的台阶编号）
    • 如果当前台阶不能爬，即blocked.containsKey(i)，就将当前爬法置为0。

杨辉三角

动态规划

  1. 定义状态：dp[i][j]表示第i行第j列的数字，第i行有i+1列。
  2. 状态转移：
    • 当j > 0且j < n-1时，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]；
    • 当j == 0，dp[i][j] = dp[i-1][j]；
    • 当j == n-1，dp[i][j] = dp[i-1][j-1]；
  3. 初始条件：dp[0][0] = 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(i + 1);
            // 每一行第一个元素一定是1
            row.add(1);
            for (int j = 1; j < i; j++) {
                row.add(dp.get(i-1).get(j-1) + dp.get(i-1).get(j));
            }
            // 每一行最后一个元素也是1
            if (i > 0){
                row.add(1);
            }
            
            dp.add(row);
        }
        return dp;
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(1)，返回值不计入。

打家劫舍

动态规划

  1. 定义状态：dp[i]表示当前能够偷盗的最大金额。
  2. 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
  3. 初始条件：dp[0] = nums[0]。
  4. 返回结果：dp[n-1]。
  5. 空间优化：用两个变量记录dp[i-1]和dp[i-2].
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rob(int[] nums) {
        int f0 = 0;
        int f1 = nums[0];
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            int f2 = Math.max(f0 + nums[i], f1);
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
}
JAVA
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

打家劫舍II

打家劫舍III

打家劫舍IV

完全平方数

动态规划

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

  1. 定义状态：f[i] 表示最少需要多少个数的平方来表示整数 i。
  2. 状态转移：枚举，从1到j*j <= i的所有j，不断更新找到使用完全平方数最少的。
  3. 初始条件f[0] = 0.
  4. 返回结果f[n]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <=n; i++) {
            int minn = Integer.MAX_VALUE;
            // 枚举完全平方数
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
}
JAVA
  • 时间复杂度：$O(n \sqrt{n})$
  • 空间复杂度：O(n)

爬楼梯和完全平方数都有一些数学方法可以解决，有时间在看，这里主要复习动态规划的思想。

零钱兑换

动态规划

  1. 定义状态：dp[i]表示凑成金额为i需要的最少硬币个数。
  2. 状态转移：枚举硬币面值，dp[i] = min(dp[i], dp[i-num] + 1)。
  3. 初始条件：dp[i] = amount + 1,dp[0] = 0.
  4. 返回结果：dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int coinChange(int[] coins, int amount) {
        // 定义状态
        int[] dp = new int[amount + 1];
        int max = amount + 1;
        Arrays.fill(dp, max);
        // 枚举硬币
        dp[0] = 0;
        for (int num : coins) {
            // 枚举金额
            for (int i = num; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i-num] + 1);
            }
        }
        // 返回结果
        return dp[amount] == max ? -1 : dp[amount];
    }
}
JAVA
  • 时间复杂度：$O(n \cdot amount)$
  • 空间复杂度：O(amount)

也可以把枚举金额放在外套循环，但是就需要在循环中判断硬币的面值是否比需要凑成的金额小。

单词拆分

动态规划

  1. 定义状态：dp[i]表示前i个字符能否用列表中的单词表示。
  2. 状态转移：如果s[0:j]可以拆分，即dp[j]=true，并且s[j:i]出现在字典中，则dp[i] = true。如果s[0:j]不可以拆分，或者s[j:i]没有出现在字典中，则dp[i] = false。
  3. 初始条件：长度为0的字符串可以拆分为单词，dp[0] = true。
  4. 返回结果dp[n]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 定义状态
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        // 将单词存入哈希表以便用O(1)时间查找
        HashSet<String> set = new HashSet<>(wordDict);

        // 填表
        for (int i = 1; i <= n; i++) {
            // 枚举切分位置
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }

        return dp[n];
    }
}
JAVA
  • 时间复杂度：$O(n ^ 2)$，一共有 O(n) 个状态需要计算，每次计算需要枚举 O(n) 个分割点，哈希表判断一个字符串是否出现在给定的字符串列表需要 O(1) 的时间。
  • 空间复杂度：O(n)

最长递增子序列

动态规划

  1. 定义状态：dp[i]表示以nums[i]为结尾的最长递增子序列长度。
  2. 状态转移：枚举j，如果nums[i] > nums[j]，则更新状态dp[i] = max(dp[i], dp[j] + 1)。
  3. 初始条件：dp[i] = 1，以nums[i]结尾的子序列初始长度是1.
  4. 返回结果：维护一个最大值变量，返回它。
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 lengthOfLIS(int[] nums) {
        // 定义状态
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;
        // 枚举数字
        for (int i = 1; i < n; i++) {
            // 枚举上一个序列位置
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新答案变量
            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(n)

贪心+二分查找

可以进一步优化时间复杂度：如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

  • 维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。
  • 从前往后遍历数组 nums，在遍历到 nums[i] 时：
    • 如果 nums[i]>d[len] ，则直接加入到 d 数组末尾，并更新 len=len+1；
    • 否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k+1]=nums[i]。如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1].
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
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int len = 1;
        // 定义数组d并初始化
        int[] d = new int[n + 1];   // 因为len最多是n
        d[len] = nums[0];           // 长度为1的子序列最小的末尾元素初始化为nums[0]
        // 遍历数组
        for (int i = 1; i < n; i++) {
            // 如果当前数字比末尾元素大，说明序列可以加长
            if (nums[i] > d[len]){
                d[++len] = nums[i];
                continue;
            }
            // 否则进行二分查找，找到该更新的位置
            int left = 1, right = len, pos = 0;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (d[mid] < nums[i]) {
                    pos = mid;  // nums[i] 可以替代位置mid+1位置上的元素
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            d[pos + 1] = nums[i];
        }

        return len;
    }
}
JAVA
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：O(n)

乘积最大子数组

动态规划

不满足最优子结构，考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。因此维护两个数组，一个记录最大值，一个记录最小值。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。

  1. 定义状态：fmax[i]表示以nums[i]为结尾的连续子数组的最大值，fmin[i]为最小值。
  2. 状态转移：
    • fmax = max(fmax[i-1] * nums[i], fmin[i-1] * nums[i], nums[i])
    • fmin = min(fmin[i-1] * nums[i], fmax[i-1] * nums[i], nums[i])
  3. 初始条件：fmax[0] = fmin[0] = nums[0]。
  4. 返回结果：维护一个最大值变量。
  5. 空间优化：可以用两个变量代替fmax[i-1]和fmin[i-1].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProduct(int[] nums) {
        // 定义状态
        int n = nums.length;
        int fmin = nums[0];
        int fmax = nums[0];
        int ans = fmax;
        // 状态转移
        for (int i = 1; i < n; i++) {
            // 更新状态
            int tmin = Math.min(fmin * nums[i], Math.min(fmax * nums[i], nums[i]));
            int tmax = Math.max(fmax * nums[i], Math.max(fmin * nums[i], nums[i]));
            fmin = tmin;
            fmax = tmax;
            ans = Math.max(ans, fmax);
        }
        return ans;
    }
}
JAVA
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

分割等和子集

动态规划

首先计算数组中所有数字之和sum，如果它是奇数，说明无法分割。否则可以转化成背包问题，即target = sum / 2，物品重量就是数字，如果能够找到物品使其累加之和等于sum/2，则说明可以分割，否则无法分割。

  1. 定义状态：dp包含 n 行 target+1 列，其中 dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。
  2. 状态转移：外层循环枚举物品重量，内层循环枚举和：
    • 如果j >= nums[i]，可以选取也可以不选取，两种情况只要有一个为 true，就有 dp[i][j]=true。
    • 否则，dp[i][j] = dp[i-1][j]。
  3. 初始条件：初始时，dp 中的全部元素都是 false。如果不选取任何正整数，则被选取的正整数之和等于 0。因此对于所有 0≤i<n，都有 dp[i][0]=true。当 i==0 时，只有一个正整数 nums[0] 可以被选取，因此 dp[0][nums[0]]=true。
  4. 返回结果：dp[n-1][target]。
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
33
34
35
36
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        // 计算和
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;

        // 定义状态
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;    // 目标为0可以凑成
            // 还有一种情况无法凑成，即某个元素大于target
            if (nums[i] > target) {
                return false;
            }
        }
        
        dp[0][nums[0]] = true; // 第0个物品可以
        for (int i = 1; i < n; i++) {
            for(int j = 1; j <= target; j++) {
                if (j >= nums[i]) {
                    dp[i][j] = dp[i-1][j] | dp[i-1][j- nums[i]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n-1][target];
    }
}
JAVA
  • 时间复杂度：$O(n \cdot target)$
  • 空间复杂度：$O(n \cdot target)$

空间优化：

在计算 dp 的过程中，每一行的 dp 值都只与上一行的 dp 值有关，因此只需要一个一维数组即可将空间复杂度降到 O(target)。

此时状态转移方程为：dp[j]=dp[j] ∣ dp[j−nums[i]]。第二层的循环我们需要从大到小计算，因为如果我们从小到大更新 dp 值，那么在计算 dp[j] 值的时候，dp[j−nums[i]] 已经是被更新过的状态，不再是上一行的 dp 值。

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
33
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        // 计算和
        int sum = 0, maxNum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            maxNum = Math.max(maxNum, nums[i]);
        }
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }

        // 定义状态
        boolean[] dp = new boolean[target + 1];
        
        dp[nums[0]] = true; // 第0个物品可以
        for (int i = 1; i < n; i++) {
            for(int j = target; j >= 0; j--) {
                if (j >= nums[i]) {
                    dp[j] = dp[j] | dp[j- nums[i]];
                } else {
                    dp[j] = dp[j];
                }
            }
        }
        return dp[target];
    }
}
JAVA
  • 时间复杂度：$O(n \cdot target)$
  • 空间复杂度：O(target)

最长有效括号

动态规划

  1. 定义状态：dp[i]表示以字符s[i]为结尾的最长有效子串长度。
  2. 状态转移：
    • 如果s[i] == '('，则以s[i]为结尾的字符串不可能是有效括号子串，dp[i] = 0。
    • 如果s[i] == ')'，需要考虑 s[i - 1] 来判断是否能够构成有效括号对：
      • 如果s[i-1] == '('，则dp[i] = dp[i-1] + 2
      • 如果s[i-1] == ')'，则我们需要看 i - 1 - dp[i - 1] 位置上的字符 s[i - 1 - dp[i - 1]]是否与 s[i] 匹配:
        • 如果是右括号，那就不匹配。
        • 如果是左括号，则匹配，那么需要看以 s[i - 1 - dp[i - 1]] 的前一个字符 s[i - 2 - dp[i - 1]] 为结尾的最长括号长度是多少，即dp[i] = dp[i-1] + dp[i-2-dp[i-1]] + 2，如果i-2-dp[i-1] < 0，即不存在，那么dp[i] = dp[i-1] + 2`。
  3. 初始条件：dp[0] = 0，一个字符无法构成有效的括号。
  4. 发你结果：维护一个最大值变量。
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
class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n < 2) {
            return 0;
        }

        // 定义状态
        int[] dp = new int[n];
        int ans = 0;
        // 状态转移
        for (int i = 1; i < n; i++) {
            char c = s.charAt(i);
            // 如果是右括号，则需要更新状态
            if (c == ')') {
                // 如果前一个字符是左括号，直接匹配
                if (s.charAt(i-1) == '(') {
                    dp[i] = (i < 2 ? 0 : dp[i-2]) + 2;
                } 
                // 需要看 i - 1 - dp[i - 1] 位置上的字符是否匹配
                else if (i-1-dp[i-1] >= 0 && s.charAt(i-1-dp[i-1]) == '('){
                    dp[i] = dp[i-1] + (i - 2 - dp[i-1] >= 0 ? dp[i-2-dp[i-1]] : 0) + 2;
                }
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }
}
JAVA
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

栈

始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」。

  • 初始化栈，放入-1。
  • 如果是左括号，就把其下标入栈。
  • 如果是右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    • 如果不为空，说明有匹配的括号，出栈，然后可以更新最大长度ans = max(ans, i - 栈顶下标)。
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
class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int ans = 0;
        // 定义栈并初始化
        Deque<Integer> stk = new ArrayDeque<>();
        stk.push(-1);
        // 遍历元素
        for (int i = 0; i < n; i++) {
            // 左括号入栈
            if (s.charAt(i) == '(') {
                stk.push(i);
            } else {
                // 出栈
                stk.pop();
                if (stk.isEmpty()) {
                    // 栈为空，将当前右括号作为最后一个未匹配的
                    stk.push(i);
                } else {
                    // 更新最大长度
                    ans = Math.max(ans, i - stk.peek());
                }
            }
        }
        return ans;
    }
}
JAVA
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

不需要额外空间

利用两个计数器 left 和 right 。首先，我们从左到右遍历字符串，对于遇到的每个 ‘(’，我们增加 left 计数器，对于遇到的每个 ‘)’ ，我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。

只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

  • 当 left 计数器比 right 计数器大时，我们将 left 和 right 计数器同时变回 0
  • 当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串
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
33
34
35
36
37
38
class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int left = 0, right = 0, ans = 0;
        // 从左到右
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            // 更新计数器
            if (left == right) {
                ans = Math.max(ans, left + right);
            } else if (right > left) {
                left = 0;
                right = 0;
            }
        }
        // 从右到左
        left = right = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            // 更新计数器
            if (left == right) {
                ans = Math.max(ans, left + right);
            } else if (left > right) {
                left = 0;
                right = 0;
            }
        }
        return ans;
    }
}
JAVA
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

不同路径

动态规划

  1. 定义状态：dp[i][j]表示当前位置有多少条不同的路径。
  2. 状态转移：dp[i][j] = dp[i-1][j] + dp[j-1][i]。
  3. 初始条件：dp[0][j] = 1. dp[i][0] = 1.
  4. 返回结果：dp[m-1][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int uniquePaths(int m, int n) {
        // 定义状态并初始化
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        // 状态转移
        for (int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
}
JAVA
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

空间优化

由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int uniquePaths(int m, int n) {
        // 定义状态并初始化
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        // 状态转移
        for (int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[j] += dp[j-1];
            }
        }

        return dp[n-1];
    }
}
JAVA
  • 时间复杂度：O(mn)
  • 空间复杂度：O(1)

组合数学

从左上角到右下角的过程中，我们需要移动 m+n−2 次，其中有 m−1 次向下移动，n−1 次向右移动。因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数，即组合数：

1
2
3
4
5
6
7
8
9
class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; x++, y++) {
            ans = ans * x / y;
        }
        return (int)ans;
    }
}
JAVA
  • 时间复杂度：O(m)
  • 空间复杂度：O(1)

最小路径和

动态规划

  1. 定义状态：dp[i][j]表示走到i,j位置的最小路径和。
  2. 状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1])。
  3. 初始条件：dp[0][0] = grid[0][0]
  4. 返回结果：dp[m-1][n-1]
  5. 空间优化：只与上一行有关，可以用滚动数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 定义状态
        int[] dp = new int [n];
        dp[0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1] + grid[0][i];
        } 
        // 状态转移
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];
            for(int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
            }
        }

        return dp[n-1];
    }
}
JAVA
  • 时间复杂度：O(mn)
  • 空间复杂度：O(n)

最长回文子串

动态规划

  1. 定义状态：dp[i][j]表示s[i:j]是否是回文的。
  2. 状态转移：$s[i] = s[j], dp[i][j] = \begin{cases} true & j-i \leq 2 \cr dp[i+1][j - 1] & else \end{cases}$
  3. 初始条件：dp[i][j] = false.
  4. 返回结果：维护一个最大长度变量和起始点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int maxStart = 0, maxLen = 1;
        // 定义状态
        boolean[][] dp = new boolean[n][n];
        // 枚举结束位置
        for (int j = 1; j < n; j++) {
            // 枚举起始位置
            for (int i = 0; i < j; i++) {
                // 更新状态
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = j - i <= 2 ? true : dp[i+1][j-1];
                    if (dp[i][j] && j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        maxStart = i;
                    }
                }
            }
        }
        return s.substring(maxStart, maxStart + maxLen);
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

中心扩散法

从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。

  1. 首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
  2. 然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
  3. 最后左右双向扩散，直到左和右不相等。
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
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int maxStart = 0, maxLen = 0;
        // 枚举每个中心位置
        for (int i = 0; i < n; i++){
            // 定义左右指针
            int left = i - 1, right = i + 1;
            // 向左扩展
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
            }
            // 向右扩展
            while (right < n && s.charAt(right) == s.charAt(i)) {
                right++;
            }
            // 向两边扩展
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            // 更新状态
            if (right - left - 1 > maxLen) {
                maxLen = right - left - 1;  // 因为此时left和right都更新到了
                maxStart = left + 1;
            }
        }
        return s.substring(maxStart, maxStart + maxLen);
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(1)

Manacher 算法

  1. 预处理字符串：为了统一奇数长度和偶数长度的回文子串，使用特殊字符（如 #）在字符串之间插入。例如，字符串 “aba” 被处理为 “#a#b#a#”。
  2. 回文半径数组：定义一个数组 p，其中 p[i] 表示以 i 为中心的回文子串的半径（包括中心）。
  3. 中心扩展和边界：使用两个变量 center 和 right 分别记录当前扩展的回文子串的中心和右边界。
    • 如果 i 在 right 范围内，则可以利用对称性确定初始半径。
    • 否则，通过尝试扩展来更新半径。
  4. 扩展优化：在每次尝试扩展时，更新 center 和 right。
  5. 结果提取：遍历 p 数组，找到最大半径值及其对应的位置，从而提取最长回文子串。
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public String longestPalindrome(String s) {
        // 预处理字符串
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for (char c : s.toCharArray()) {
            sb.append(c);
            sb.append("#");
        }
        String t = sb.toString();      

        // 回文数组p
        int n = t.length();
        int[] p = new int[n];

        // 中心扩展和边界
        int center = 0, right = 0, maxIndex = 0, maxLen = 0;
        for (int i = 0; i < n; i++){
            // 利用对称性初始化 p[i]
            int mirror = 2 * center - i;
            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            }
            // 尝试扩展来更新半径
            int a = i - p[i] - 1;
            int b = i + p[i] + 1;
            while (a >= 0 && b < n && t.charAt(a) == t.charAt(b)){
                p[i]++;
                a--;
                b++;
            }
            // 在每次尝试扩展时，更新 center 和 right
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            if (p[i] > maxLen) {
                maxIndex = i;
                maxLen = p[i];
            }
        }
        // 提取原字符串中的最长回文子串
        int start = (maxIndex - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }
}
JAVA
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

最长公共子序列

动态规划

  1. 定义状态：：dp[i-1][j-1]等于以text1前i个字符和text2以前j个字符的子序列长度。
  2. 状态转移：
    • 如果text1[i] == text2[j]，dp[i][j] = dp[i-1][j-1] + 1
    • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  3. 初始条件：dp[i][0] = dp[0][j] = 0；
  4. 返回结果：dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // 定义状态
        int[][] dp = new int[m + 1][n + 1];
        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    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];
    }
}
JAVA
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

编辑距离

动态规划

  1. 定义状态：dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需要的最少操作数。
  2. 状态转移：如果word1[i-1] ！= word2[j-1]，
    • 插入：dp[i-1][j] + 1
    • 删除：dp[i][j-1] + 1
    • 替换：dp[i-1][j-1] + 1
    • 三种情况取最小值
  3. 初始条件：dp[0][0] = 0，无需操作，dp[0][j] = j，dp[i][0] = i。
  4. 返回结果：dp[m][n]
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
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        // 定义状态
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                }
                
            }
        }
        return dp[m][n];
    }
}
JAVA
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)
算法笔记 > 动态规划
#leetcode-hot100
LeetCode 热题 100-动态规划
http://example.com/2024/12/19/posts/hot100-15/
作者
Xuan Yang
发布于
2024年12月19日
许可协议