动态规划概述与基本思想

1. 动态规划简介

动态规划（Dynamic Programming，简称DP）是一种求解复杂问题的方法，它通过将一个大问题分解为多个小问题，然后逐步解决这些小问题，最后将它们的解合并以得到原问题的解。其核心思想是记忆化（或称为“备忘录”）——通过存储已经解决过的子问题的结果，避免重复计算，从而提高算法的效率。

动态规划与分治法有相似之处，它们都采用分解问题的方法。然而，分治法将问题分解成多个独立的子问题，而动态规划则是将问题分解成多个互相重叠的子问题，子问题之间存在依赖关系。在动态规划中，我们需要保存并复用子问题的结果，这样就避免了重复计算，提高了效率。

2. 动态规划的应用场景

动态规划适用于具有重叠子问题和最优子结构的场景。

重叠子问题：问题的子问题不是完全独立的，而是会重复出现，因此可以通过存储之前计算过的结果来避免重复计算。
最优子结构：问题的最优解可以通过子问题的最优解来构造。例如，一个最短路径问题的最优解可以通过其子路径的最优解得到。

典型的动态规划问题包括：

最短路径问题：例如在图中寻找从起点到终点的最短路径（Dijkstra算法、Floyd算法）。
背包问题：在给定的物品和背包容量下，选择若干物品使得总价值最大，且总重量不超过背包容量（0/1背包问题）。
最长公共子序列问题：给定两个字符串，求它们的最长公共子序列。

这些问题中，子问题的解常常可以通过合并之前的解来获得，这正是动态规划的核心。

3. 动态规划的基本思想

动态规划的核心思想可以通过三个关键概念来描述：

自底向上：
- 动态规划从解决小问题开始，然后逐渐解决更大、更复杂的问题。这是自底向上的特点。通过解决最简单的子问题，我们可以得到更大的问题的解。
重叠子问题：
- 在动态规划中，很多子问题会多次出现，计算的结果可以被缓存并重复使用，从而避免重复计算。这个思想类似于分治法中的“重叠”问题，但不同的是，动态规划会保存并复用这些结果。
最优子结构：
- 最优子结构是指问题的最优解可以通过子问题的最优解来构建。也就是说，问题的解可以通过递归地将子问题的解组合起来得到。对于动态规划问题，我们通过不断地扩展子问题的解来最终得到整个问题的最优解。

4. 动态规划与贪心算法的区别

动态规划和贪心算法都能用来求解优化问题，但它们的策略和适用条件是不同的：

贪心算法：
- 贪心算法每次做出局部最优的选择，它只关注当前最好的选项，而不考虑后续的选择。贪心算法的目标是通过局部最优解的累积来得到全局最优解，但它不能保证一定能得到全局最优解。因此，贪心算法适用于一些满足“贪心选择性质”的问题，也就是说，局部最优选择能够保证全局最优。
动态规划：
- 动态规划则通过考虑全局的最优解，逐步求解每个子问题，最终合并子问题的解得到整体问题的最优解。动态规划不仅仅关心当前的选择，还会回溯并考虑历史选择，确保得到的解是全局最优的。

4.1 何时选择贪心，何时使用动态规划？

如果一个问题的贪心选择性质成立（即通过局部最优解可以得到全局最优解），那么可以使用贪心算法。例如，活动选择问题、霍夫曼编码问题等。
如果问题的最优解需要通过全局考虑和子问题的最优解来构建，那么就需要使用动态规划。比如背包问题、最长公共子序列问题等。

4.2 贪心与动态规划的选择：

贪心算法：求局部最优解，适用于简单的优化问题。
动态规划：求全局最优解，适用于复杂的最优化问题和具有重叠子问题的场景。

5. 代码案例：经典的动态规划问题——爬楼梯

5.1 问题描述：

假设一个人正在爬楼梯，每次可以选择爬 1 步或 2 步，问到达楼顶的不同方法有多少种。假设楼梯总共有 n 个阶梯。

5.2 解决思路：

这个问题可以通过动态规划来求解。我们可以通过将问题分解为子问题来解决。设 dp[i] 表示爬到第 i 个楼梯的方法数。那么，状态转移方程为：

dp[i] = dp[i-1] + dp[i-2] 也就是说，要到达第 i 个楼梯，可以从第 i-1 个楼梯跳 1 步，或者从第 i-2 个楼梯跳 2 步。

5.3 代码实现：

public class ClimbingStairs {
    public int climbStairs(int n) {
        // 边界条件
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        // 动态规划数组，dp[i] 表示爬到第 i 个楼梯的方案数
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        // 从第 3 个楼梯开始，逐步计算
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
        }
        
        // 返回到达第 n 个楼梯的方案数
        return dp[n];
    }
}

5.4 代码解释：

定义dp数组：dp[i]表示到达第 i 个楼梯的方案数。
边界条件：当楼梯只有 1 或 2 个时，爬楼的方法数分别为 1 和 2。
状态转移：从第 3 个楼梯开始，通过状态转移方程 dp[i] = dp[i-1] + dp[i-2] 逐步计算每个楼梯的方案数。
返回结果：返回 dp[n] 即为到达第 n 个楼梯的总方案数。

5.5 时间复杂度与空间复杂度：

时间复杂度：O(n)，我们只需要一次遍历计算所有的 dp 值。
空间复杂度：O(n)，需要一个长度为 n 的数组来存储每个楼梯的方案数。

6. 总结

动态规划是一种通过分解问题来求解复杂问题的算法。它适用于具有重叠子问题和最优子结构的场景。在解决动态规划问题时，我们通常需要通过状态转移方程来确定问题的解，并通过自底向上的方法逐步解决每个子问题，从而得到最终的解。动态规划与贪心算法的主要区别在于动态规划关注全局最优解，而贪心算法关注局部最优解。通过判断问题是否具有重叠子问题和最优子结构，我们可以决定使用贪心算法还是动态规划来解决问题。

去1:1私密咨询