面试经典 150 题-动态规划

LeetCode 面试经典 150 题-动态规划

打家劫舍

动态规划

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]。

class Solution {
    public int rob(int[] nums) {
        int f0 = 0, f1 = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int f2 = Math.max(f0 + nums[i], f1);
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

打家劫舍II

动态规划

和上一题的区别是第一间房屋和最后一间房屋不能同时打劫。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0,n−2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1,n−1]。

class Solution {
    public int rob(int[] nums) {
        // 边界处理
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // 返回两种情况的较大值
        return Math.max(robRange(nums, 0, n-2), robRange(nums, 1, n-1));
    }

    public int robRange(int[] nums, int start, int end) {
        // 初始化
        int f0 = nums[start], f1 = Math.max(nums[start], nums[start+1]);
        // 动态规划
        for (int i = start + 2; i <= end; i++) {
            int f2 = Math.max(f0 + nums[i], f1);
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

打家劫舍III

动态规划

1. 定义状态：f表示选中当前节点的最大金额，g表示不选中当前节点的最大金额。
2. 状态转移：如果选中当前节点，则不能选左右节点，f = g(l) + g(r)。如果不选中当前节点，则可选可不选左右节点，g = max(f(l), g(l)) + max(f(r), g(r))。
3. 初始条件：都是0.
4. 返回结果：max(f, g)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] ans = dfs(root);
        return Math.max(ans[0], ans[1]);
    }

    public int[] dfs(TreeNode node) {
        // 递归结束
        if (node == null) {
            return new int[]{0,0};
        }
        // 递归遍历左右节点
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int selected = node.val + left[1] + right[1];
        int nonSelected = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{selected, nonSelected};
    }
}

• 时间复杂度：O(n)，相当于对树进行了一次后序遍历。
• 空间复杂度：O(n)，栈空间消耗。

打家劫舍IV

单词拆分

动态规划

1. 定义状态：dp[i]表示前i个字符能否被拆分成单词。
2. 状态转移：如果s[0:j]能被拆分，即dp[j]==true，且s[j:i]在单词列表中，则dp[i]为true，否则为false。
3. 初始条件：长度为0的字符串可以拆分为单词，dp[0] = true。
4. 返回结果：dp[n]。

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] == true && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        // 返回结果
        return dp[n];
    }
}

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

零钱兑换

动态规划

1. 定义状态：dp[i]表示凑成i元所需要的最少硬币数。
2. 状态转移：枚举硬币面值，dp[i] = min(dp[i], dp[i-num]+1)。
3. 初始条件：dp[i] = amount+1，dp[0] = 0，凑成0需要0个硬币。
4. 返回结果：如果dp[amount]等于amount+1，说明不符合条件，返回-1，否则返回dp[amount]。

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 coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i-coin] + 1);
            }
        }
        // 返回结果
        return dp[amount] == max ? -1 : dp[amount];
    }
}

• 时间复杂度：$O(n \times amount)$
• 空间复杂度：O(amount)

最长递增子序列

动态规划

1. 定义状态：dp[i]表示以nums[i]为结尾的最长递增子序列。
2. 状态转移：枚举j，如果nums[i] > nums[j]，更新状态dp[i] = max(dp[i], dp[j] + 1)。
3. 初始条件：dp[i] = 1.
4. 返回结果：维护一个最大值变量，记录过程中的最长递增子序列长度。

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;
    }
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：O(n)

三角形最小路径和

动态规划

1. 定义状态：dp[j]表示到达当前行第i列的最小路径和。
2. 状态转移：第i行有i+1个数字，如果j > 0，dp[j] = min(dp[j-1], dp[j]) + triangle[i][j]；否则dp[j] = dp[j] + triangle[i][j]。
3. 初始条件：dp[0] = triangle[0][0]。
4. 返回结果：最后一行dp最小值。
5. 空间优化：使用滚动数组，从后往前更新保证不会被覆盖。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // 定义状态
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = triangle.get(0).get(0);
        // 枚举行
        for (int i = 1; i < n; i++) {
            // 枚举列
            for (int j = i; j > 0; j--) {
                // 更新状态
                dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
            }
            dp[0] += triangle.get(i).get(0);
        }
        // 更新结果
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[i]);
        }

        return ans;
    }
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：O(n)

最小路径和

动态规划

1. 定义状态：dp[j]表示走到当前行第j列的最小路径和。
2. 状态转移：dp[0] = dp[0] + grid[i][0]，dp[j] = min(dp[j-1], dp[j]) + grid[i][j]。
3. 初始条件：第一行只能是向右走得到的，即dp[j] = dp[j-1] + grid[0][j]。
4. 返回结果：dp[n-1]。

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 j = 1; j < n; j++) {
            dp[j] = dp[j-1] + grid[0][j];
        }
        // 枚举行
        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-1], dp[j]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
}

• 时间复杂度：$O(mn)$
• 空间复杂度：O(n)

不同路径II

动态规划

1. 定义状态：dp[j]表示走到当前行第j列的路径数。
2. 状态转移：如果grid[i][j] == 1，则无法到达当前位置，dp[j] = 0.否则，dp[0] += 1，dp[j] += dp[j-1]。
3. 初始条件：第一行只能是向右走得到的，即dp[j] = 1，但如果存在一个位置有障碍物，其后的都为0。
4. 返回结果：dp[n-1]。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        // 定义状态
        int[] dp = new int[n];
        dp[0] = (obstacleGrid[0][0] + 1) % 2;
        // 初始化第一行的状态
        for (int i = 1; i < n; i++) {
            if (obstacleGrid[0][i] == 1) {
                dp[i] = 0;
            } else {
                dp[i] = dp[i-1];
            }
        }
        
        // 从第二行开始枚举
        for (int i = 1; i < m; i++) {
            // 特别处理第一列
            if (obstacleGrid[i][0] == 1) {
                dp[0] = 0;  // 如果第一列有障碍物，dp[0]设置为0
            }
            
            // 枚举当前行的列
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;  // 如果当前格子有障碍物，dp[j]设置为0
                } else {
                    dp[j] = dp[j-1] + dp[j];  // 否则累加来自左边和上边的路径数
                }
            }
        }
        
        // 返回右下角的路径数
        return dp[n-1];
    }
}

• 时间复杂度：$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. 返回结果：维护一个最大长度变量和起始点。

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) || 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);
    }
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

中心扩散法

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

1. 首先往左寻找与当前位置相同的字符，直到遇到不相等为止。
2. 然后往右寻找与当前位置相同的字符，直到遇到不相等为止。
3. 最后左右双向扩散，直到左和右不相等。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int maxStart = 0, maxLen = 1;
        // 枚举每个中心位置
        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;
                maxStart = left + 1;
            }
        }
        // 返回结果
        return s.substring(maxStart, maxStart + maxLen);
    }
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：O(1)

Manacher 算法

很难理解，之后看看之前做的。

交错字符串

动态规划

1. 定义状态：dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前i+j个字符。
2. 状态转移：如果s1[i] == s3[i+j]，则dp[i][j] = dp[i-1][j]；如果s2[j] == s3[i+j]，则dp[i][j] = dp[i][j-1]。
3. 初始条件：dp[0][0] = true。
4. 返回结果：dp[m][n]。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // 边界处理
        int m = s1.length();
        int n = s2.length();
        int t = s3.length();
        if (m + n != t) {
            return false;
        }
        // 定义状态
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        // 枚举s1
        for (int i = 0; i <= m; i++){
            // 枚举s2
            for (int j = 0; j <= n; j++) {
                int p = i + j - 1;
                if (i > 0) {
                    dp[i][j] = dp[i][j] || (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(p));
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(p));
                }
            }
        }
        return dp[m][n];
    }
}

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

空间优化

使用滚动数组优化空间：

1. 定义状态：dp[j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前i+j个字符。
2. 状态转移：如果s1[i] == s3[i+j]，则dp[j] = dp[j]；如果s2[j] == s3[i+j]，则dp[j] = dp[j-1]。
3. 初始条件：dp[0] = true。
4. 返回结果：dp[n]。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // 边界处理
        int m = s1.length();
        int n = s2.length();
        int t = s3.length();
        if (m + n != t) {
            return false;
        }
        // 定义状态
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        // 枚举s1
        for (int i = 0; i <= m; i++){
            // 枚举s2
            for (int j = 0; j <= n; j++) {
                int p = i + j - 1;
                if (i > 0) {
                    dp[j] &= (s1.charAt(i - 1) == s3.charAt(p)); 
                }
                if (j > 0) {
                    dp[j] |= (dp[j-1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }
        return dp[n];
    }
}

• 时间复杂度：O(mn)
• 空间复杂度：O(n)

编辑距离

动态规划

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]。

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];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        // 枚举word1
        for (int i = 1; i <= m; i++) {
            // 枚举word2
            for (int j = 1; j <= n; j++) {
                // 状态转移
                if (word1.charAt(i-1) != word2.charAt(j-1)) {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                } else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        // 返回结果
        return dp[m][n];
    }
}

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

买卖股票的最佳时机III

动态规划

1. 定义状态：buy1、sell1、buy2、sell2，表示每次操作后得到的利润。
2. 状态转移
   • buy1 = max(buy1, -prices[i])；
   • sell1 = max(sell1, buy1 + prices[i])；
   • buy2 = max(buy2, sell1 - prices[i]);
   • sell2 = max(sell2, buy2 + prices[i]);
3. 初始条件：
   • buy1 = -prices[0]
   • sell1 = 0 表示同一天买入又卖出
   • buy2 = -prices[0] 表示同一天买入又卖出又买入
   • sell2 = 0 表示同一天买入又卖出又买入又卖出
4. 返回结果：max(0, sell1, sell2)，如果最优的情况对应的是恰好一笔交易，那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件，从 sell1转移至sell2，因此最终返回sell2即可。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 定义状态
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        // 枚举价格
        for (int i = 1; i < n; i++) {
            // 状态转移
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        // 返回结果
        return sell2;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

买卖股票的最佳时机IV

动态规划

1. 定义状态：dp[j][0]表示第j次交易后不持有股票的最大利润，dp[j][1]表示第j次交易后持有股票的最大利润。
2. 状态转移：注意，j从后向前遍历，可以避免覆盖上一轮的状态。
   • dp[j][0] = max(dp[j-1][0], dp[j-1][1] + prices[i])
   • dp[j][1] = max(dp[j-1][1], dp[j-1][0] - prices[i])
3. 初始条件：dp[j][0] = 0，dp[j][1] =负无穷.
4. 返回结果：dp[k][0]。

取k值部分是因为，一共有n个价格，最多交易次数就是n/2，因此k>n/2没有意义。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        
        // dp[j][0] 表示进行 j 次交易后，不持有股票的最大利润
        // dp[j][1] 表示进行 j 次交易后，持有股票的最大利润
        k = Math.min(k, n / 2);
        int[][] dp = new int[k + 1][2];
        
        // 初始化：进行 0 次交易时，不持有股票最大利润为 0，持有股票的最大利润为负无穷
        for (int j = 0; j <= k; j++) {
            dp[j][1] = Integer.MIN_VALUE; // 初始化持有股票的最大利润为负无穷
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = k; j > 0; j--) {
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]); // 不持有股票时的最大利润
                dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]); // 持有股票时的最大利润
            }
        }
        
        return dp[k][0]; // 返回最大利润，即进行 k 次交易后，不持有股票的最大利润
    }
}

• 时间复杂度：$O(n \cdot min(n,k))$
• 空间复杂度：$O(min(n,k))$

最大正方形

动态规划

1. 划分阶段：按照正方形的右下角坐标进行阶段划分。
2. 定义状态：dp[i][j]表示以(i,j)为右下角的且值包含1的正方形的最大边长。
3. 状态转移方程：如果matrix[i][j] == 0，则dp[i][j] = 0；否则dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
4. 初始条件：dp[i][j] = 0。边界条件：i == 0 || j == 0。即当matrix[i][j] = 0时，无需进行操作，因为初始化为0，如果是1，再根据是否是边界情况来进行不同的操作。
5. 返回结果：维护一个最大值变量，然后取其平方。

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 定义状态
        int[][] dp = new int[m][n];
        // 枚举行
        int ans = 0;
        for (int i = 0; i < m; i++) {
            // 枚举列
            for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                    // 处理边界
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    ans = Math.max(ans, dp[i][j]);                    
                }
            }
        }
        // 返回结果
        return ans * ans;
    }
}

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

总结

面试150题除了前缀树基本都做完了，和hot100有大量重合的题目。之后就不再刷leetcode了，开始找真题刷，然后每天复习之前做过的这些经典题目。