LeetCode Day动态编程第 2 部分

动态规划是一种解决复杂问题的有效方法，它通过将问题分解成较小的子问题来简化计算。尤其是在LeetCode这样的编程练习平台上，动态规划相关的问题频繁出现，成为许多程序员在求职面试中的重点考察内容。在这篇文章中，我们继续深入动态规划的世界，聚焦于一些经典问题及其解法。

动态规划的基本概念

动态规划（Dynamic Programming, DP）是将大的问题划分为小的问题并保存解决方案的方法。这种方法依赖于两个主要特性：重叠子问题和最优子结构。重叠子问题意味着在解决过程中会多次计算同一子问题，而最优子结构则意味着一个问题的最优解可以由其子问题的最优解构成。

重叠子问题

在动态规划中，重叠子问题可以通过记忆化递归或自下而上的表格填充来避免重复计算。记忆化递归会存储已经计算过的结果，避免再次计算相同的子问题。

最优子结构

最优子结构则强调解决一个问题的最优解是由其子问题的最优解构成的。这种结构使得动态规划可以通过简单的状态转移方程得出结果。

动态规划常见问题解析

现在我们将讨论一些常见的动态规划问题，以及如何通过动态规划进行求解。这些问题不仅在LeetCode上出现频率高，也是面试中常被提及的经典例题。

爬楼梯问题

爬楼梯问题可以简单描述为：有n阶楼梯，每次可以爬1阶或2阶，问有多少种方法可以到达顶部。这个问题显然有重叠的子问题，可以用动态规划进行求解。

public int climbStairs(int n) {
    if (n <= 1) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

在这个解法中，dp数组用于保存到达每一阶楼梯的方法数量，最后返回dp[n]即为所求。

最长上升子序列

另一个经典的动态规划问题是寻找最长上升子序列（LIS）。给定一个整数数组，计算其中最长的严格上升子序列的长度。

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    int n = nums.length;
    int[] dp = new int[n];
    int maxLength = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;  // 每个单独的元素至少构成长度为1的上升子序列
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    return maxLength;
}

在这个解法中，我们使用一个dp数组，其中dp[i]表示以nums[i]为终点的最长上升子序列的长度。通过两层循环，更新每一个数字的最长上升子序列长度，最终找到最大值。

总结与展望

动态规划是一种强大的方法，能够有效地处理许多复杂问题。通过不断练习这些常见的动态规划题目，我们可以加深对这一算法的理解。在LeetCode上，你还会遇到众多其他动态规划题，挑战自己并不断提升是每位程序员应当追求的目标。在未来，我们还可以探索更高级的动态规划题，以及如何将动态规划与其他算法结合，解决更复杂的问题。