看一遍就理解：动态规划详解
看一遍就理解：动态规划详解
动态规划是算法领域一个非常重要且经典的概念，广泛应用于各种优化问题的求解。本文将从基础概念出发，通过具体案例深入讲解动态规划的核心思想、解题套路以及实际应用，帮助读者系统性地掌握这一算法技巧。
什么是动态规划？
动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
简单来说，动态规划就是将一个复杂问题分解成一系列子问题，通过保存子问题的解来避免重复计算，从而高效地解决问题。例如，斐波那契数列就是一个典型的动态规划问题。
动态规划的核心思想
动态规划最核心的思想在于“拆分子问题，记住过往，减少重复计算”。通过一个简单的例子来说明：
- A ： "1+1+1+1+1+1+1+1 =？"
- A ： "上面等式的值是多少"
- B ： 计算 "8"
- A : 在上面等式的左边写上 "1+" 呢？
- A : "此时等式的值为多少"
- B : 很快得出答案 "9"
- A : "你怎么这么快就知道答案了"
- A : "只要在8的基础上加1就行了"
- A : "所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"
一个例子带你走进动态规划 — 青蛙跳阶问题
暴力递归
考虑一个经典的动态规划问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。
通过分析可以发现：
- 要想跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去；要么是先跳到第8级，然后一次迈2级台阶上去。
- 同理，要想跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去；要么是先跳到第7级，然后一次迈2级台阶上去。
- 要想跳到第8级台阶，要么是先跳到第7级，然后再跳1级台阶上去；要么是先跳到第6级，然后一次迈2级台阶上去。
假设跳到第n级台阶的跳数我们定义为f(n)，可以得出以下递推公式：
f（10） = f（9）+f(8)
f (9) = f(8) + f(7)
f (8) = f(7) + f(6)
...
f(3) = f(2) + f(1)
即通用公式为: f(n) = f(n-1) + f(n-2)
边界条件为：
- 当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2；
- 当只有1级台阶时，只有一种跳法，即f（1）= 1；
使用递归实现如下：
class Solution {
public int numWays(int n) {
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return numWays(n-1) + numWays(n-2);
}
}
但是，这种暴力递归方法会遇到超时问题。通过分析递归树可以发现，存在大量重复计算：
时间复杂度分析：
- 一个子问题时间 = f（n-1）+f（n-2），也就是一个加法的操作，所以复杂度是 O(1)；
- 问题个数 = 递归树节点的总数，递归树的总节点 = 2^n-1，所以是复杂度O(2^n)。
因此，时间复杂度为 O(2^n)，对于较大的n值会非常低效。
带备忘录的递归解法（自顶向下）
为了解决重复计算问题，可以使用备忘录存储已经计算过的结果。使用一个数组或哈希map作为备忘录：
代码实现如下：
public class Solution {
//使用哈希map，充当备忘录的作用
Map<Integer, Integer> tempMap = new HashMap();
public int numWays(int n) {
// n = 0 也算1种
if (n == 0) {
return 1;
}
if (n <= 2) {
return n;
}
//先判断有没计算过，即看看备忘录有没有
if (tempMap.containsKey(n)) {
//备忘录有，即计算过，直接返回
return tempMap.get(n);
} else {
// 备忘录没有，即没有计算过，执行递归计算,并且把结果保存到备忘录map中，对1000000007取余（这个是leetcode题目规定的）
tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
return tempMap.get(n);
}
}
}
自底向上的动态规划
动态规划与带备忘录的递归解法基本思想一致，都是减少重复计算，但实现方式不同：
- 带备忘录的递归是从f(10)往f(1）方向延伸求解的，称为自顶向下的解法。
- 动态规划是从f(1)往f(10）方向，逐步决策出较大问题的解，称为自底向上的解法。
动态规划的典型特征包括：最优子结构、状态转移方程、边界、重叠子问题。在青蛙跳阶问题中：
- f(n-1)和f(n-2) 称为 f(n) 的最优子结构
- f(n)= f（n-1）+f（n-2）是状态转移方程
- f(1) = 1, f(2) = 2 是边界
- f(10)= f(9)+f(8),f(9) = f(8) + f(7) 中的f(8)是重叠子问题。
代码实现如下：
public class Solution {
public int numWays(int n) {
if (n<= 1) {
return 1;
}
if (n == 2) {
return 2;
}
int a = 1;
int b = 2;
int temp = 0;
for (int i = 3; i <= n; i++) {
temp = (a + b)% 1000000007;
a = b;
b = temp;
}
return temp;
}
}
动态规划的解题套路
什么样的问题可以考虑使用动态规划解决？
如果一个问题可以通过穷举所有可能的答案，并且发现存在重叠子问题，就可以考虑使用动态规划。常见的应用场景包括最长递增子序列、最小编辑距离、背包问题、凑零钱问题等。
动态规划的解题思路
动态规划的核心思想是“拆分子问题，记住过往，减少重复计算”，通常采用自底向上的方法。基于“青蛙跳阶”问题，总结出以下解题思路：
- 穷举分析
- 确定边界
- 找规律，确定最优子结构
- 写出状态转移方程
1. 穷举分析
- 当台阶数是1的时候，有一种跳法，f（1） =1
- 当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;
- 当台阶是3级时，想跳到第3级台阶，要么是先跳到第2级，然后再跳1级台阶上去，要么是先跳到第 1级，然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3
- 当台阶是4级时，想跳到第3级台阶，要么是先跳到第3级，然后再跳1级台阶上去，要么是先跳到第 2级，然后一次迈 2 级台阶上去。所以f(4) = f(3) + f(2) =5
- 当台阶是5级时……
2. 确定边界
通过穷举分析，发现当台阶数是1的时候或者2的时候，可以明确知道青蛙跳法。f（1） =1，f(2) = 2，当台阶n>=3时，已经呈现出规律f(3) = f(2) + f(1) =3，因此f（1） =1，f(2) = 2就是青蛙跳阶的边界。
3. 找规律，确定最优子结构
n>=3时，已经呈现出规律 f(n) = f(n-1) + f(n-2) ，因此，f(n-1)和f(n-2) 称为 f(n) 的最优子结构。最优子结构意味着让 f(n-k) 最优，使得转移到n的状态是最优的，并且与后面的决策没有关系。
4. 写出状态转移方程
通过前面3步，可以得出状态转移方程：
5. 代码实现
实现代码时，注意从底往上遍历，关注边界情况和空间复杂度。动态规划的框架通常如下：
dp[0][0][...] = 边界值
for(状态1 ：所有状态1的值){
for(状态2 ：所有状态2的值){
for(...){
//状态转移方程
dp[状态1][状态2][...] = 求最值
}
}
}
LeetCode案例分析
分析一个经典LeetCode题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
示例：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
1. 穷举分析
考虑动态规划的核心思想，需要思考原问题与子问题的关系。观察示例数据，从数组只有一个元素开始分析：
- 当nums只有一个元素10时，最长递增子序列是[10],长度是1.
- 当nums需要加入一个元素9时，最长递增子序列是[10]或者[9],长度是1。
- 当nums再加入一个元素2时，最长递增子序列是[10]或者[9]或者[2],长度是1。
- 当nums再加入一个元素5时，最长递增子序列是[2,5],长度是2。
- 当nums再加入一个元素3时，最长递增子序列是[2,5]或者[2,3],长度是2。
- 当nums再加入一个元素7时，,最长递增子序列是[2,5,7]或者[2,3,7],长度是3。
- 当nums再加入一个元素101时，最长递增子序列是[2,5,7,101]或者[2,3,7,101],长度是4。
- 当nums再加入一个元素18时，最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是4。
- 当nums再加入一个元素7时,最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是4.
2. 分析找规律，拆分子问题
发现规律：如果新加入一个元素nums[i], 最长递增子序列要么是以nums[i]结尾的递增子序列，要么就是nums[i-1]的最长递增子序列。因此：
原问题数组nums[i]的最长递增子序列 = 子问题数组nums[i-1]的最长递增子序列/nums[i]结尾的最长递增子序列
进一步分析，nums[i]结尾的最长递增子序列，只要找到比nums[i]小的子序列，加上nums[i]就可以啦。显然，可能形成多种新的子序列，我们选最长那个，就是dp[i]的值啦：
- nums[3]=5,以5结尾的最长子序列就是[2,5],因为从数组下标0到3遍历，只找到了子序列[2]比5小，所以就是[2]+[5]啦，即dp[4]=2
- nums[4]=3,以3结尾的最长子序列就是[2,3],因为从数组下标0到4遍历，只找到了子序列[2]比3小，所以就是[2]+[3]啦，即dp[4]=2
- nums[5]=7，以7结尾的最长子序列就是[2,5,7]和[2,3,7],因为从数组下标0到5遍历，找到2,5和3都比7小，所以就有[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]这些子序列，最长子序列就是[2,5,7]和[2,3,7]，它俩不就是以5结尾和3结尾的最长递增子序列+[7]来的嘛！所以，dp[5]=3 =dp[3]+1=dp[4]+1。
3. 最简单的边界情况
当nums数组只有一个元素时，最长递增子序列的长度dp(1)=1,当nums数组有两个元素时，dp(2) =2或者1, 因此边界就是dp(1)=1。
4. 确定最优子结构
从穷举分析，可以得出最优结构：
dp(i) =max(dp(j))+1，存在j属于区间[0，i-1],并且num[i]>num[j]。
5. 状态转移方程
通过前面分析，可以得出状态转移方程：
最长递增子序列 =max(dp[i])
6. 代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
//初始化就是边界情况
dp[0] = 1;
int maxans = 1;
//自底向上遍历
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
//从下标0到i遍历
for (int j = 0; j < i; j++) {
//找到前面比nums[i]小的数nums[j],即有dp[i]= dp[j]+1
if (nums[j] < nums[i]) {
//因为会有多个小于nums[i]的数，也就是会存在多种组合了嘛，我们就取最大放到dp[i]
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
//求出dp[i]后，dp最大那个就是nums的最长递增子序列啦
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}