初识动态规划

动态规划简介

1.什么是动态规划

动态规划一般简称dp，动态规划求解的问题一般可以把复杂的问题拆分一个个子问题，最终通过求解最优子结构，来得到问题的解。

2. 如何识别动态规划题目

  问题一般只会要求求出最终解或最优解，但是可以穷举出所有可能的结果集，并且穷举的过程中出现了大量的重复子计算(将在例题中说明)，。如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。
  动态规划可以很容易看出用递归实现，但是递归的存在重复的递归，使得时间复杂度很高，这时递归不被允许使用，(可以使用记忆集(List或map)，将之前计算过的答案记下来再直接使用，避免重复计算，降低时间复杂度，注意，括号内的类容不是动态规划)。

3. 动态规划解题步骤

1. 当识别出可以使用动态规划后，先尝试去写出状态转移方程。
2. 最终解：画出递归树，root节点即为要求出的最终解，找到最优解/最终解可以如何由子问题得出，以此确定状态转移方程。(最简单的是一维数组，有二维甚至多维数组)。
3. 最优解：假设i-1处的最优解为dp[i-1]，推出dp[i]处的最优解的所有可能，一般使用Math.max或Math.min的到所有可能解的最优，与dp[i]处的解比较，得出最优解。

4.动态规划例题

4.1 青蛙跳台阶问题（斐波那契数列）

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

分析(递归树略)：

1. 台阶数为1：跳法：1种。跳：1。
2. 台阶数为2：跳法：2种。跳：1 + 1、2。
3. 台阶数为3：跳法：3种。跳：1+1+1、1+2、2+1。
4. 台阶数为4：跳法：5种。跳：1+1+1+1、1+2+1、1+1+2、2+1+1、2+2。

 可以看出，在找跳法时，是存在重复计算的。例如，台阶为3时，跳了1+1+1时，计算了跳到1的情况，这时1+2，又要计算一遍跳到1的情况(每次都要从台阶1跳)。
 尝试写出转移方程：最终答案为n级台阶，那么n级台阶可以由n-1级台阶跳一级过来，也可以由n-2级台阶跳两级过来（如跳3级台阶，则可以从1级跳过来：这时跳法是1+2(如果跳1+1+1，则实际上从2级跳过来的，是重复计算，不应考虑，所以应从1直接跳到3，只能跳2级，原本只有一种跳法)，所以只有一种跳法；从2级跳过来：这时跳法是：1+1+1 (1+1 +1，前面的1+1是本来到2级台阶的方法，所以这是直接从2级台阶跳)与2+1。可以看到总跳法为两个子问题的和）。此题为求最终问题，所以得到状态转移方程：

$dp[n] = dp[n-1] + dp[n-2]$

 另外此题的递归方程也是该方程$f(n) = f(n-1) + f(n-2)$。可以很容易的写出递归求解，但是该递归的复杂度很高，时间复杂度为$2^n$，因为存在重复的递归计算。例如求f[n]时需要求解f(n-2)，再求解f(n-1)时，也需要求解f(n-2)。导致时间复杂度很高。(可以考虑使用记忆集存储)。因此不考虑，以下为动态规划解答。时间复杂度分析：O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    int[] dp = new int[n+1];
    // 基线条件
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        // 状态转移方程
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

4.2 最大连续子序列和

给定一个数组，求该数组的最大连续的子序列的和。例如[-1,-2,5-3,8,-1]，则最大子序列之和为10 ：5+(-3)+8

分析：

1. 从索引0开始穷举，一个个加，得到从索引0的最大和为7，注意，此时已经计算了一遍连续数字的和。
2. 从索引1开始穷举，一个个加，得到从索引最大的和为8，此时又计算了一遍连续数字的和。

 假设已经求出前面的dp[n-1]处的最大子序列和，这时如果dp[n]是正数，dp[n] = dp[n-1] + nums[n]，如果dp[n]是负数，肯定nums[n]单独更大，所以状态转移方程为：时间复杂度分析：O(N)

$dp[n] = max(dp[n-1] + nums[n], nums[n])$

1
2
3
4
5
6
7
8
9
10
11
12

public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxRes = nums[0];
    for (int i = 1; i < nums.length; i++) {
        // 状态转移方程(当dp[i-1] + nums[i] < num[i],即dp[i]为负数时，从nums[i]重新选)
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
        // 保存最大的解
        maxRes = Math.max(maxRes, dp[i]);
    }
    return maxRes;
}