学习笔记之动态规划

[学习笔记] 动态规划（DP，dynamic programming）

动态规划

DP, Dynamic Programming

动态规划问题的一般形式是求最值，如最长递增子序列，最小编辑距离等

求解动态规划的核心问题是穷举

• 动态规划的穷举，存在重叠子问题，需要备忘录或DP table 来优化穷举过程，避免不必要的计算
• 动态规划一定具备最优子结构
• 只有列出状态转移方程才能正确的穷举

重叠子问题、最优子结构、状态转移方程是动态规划的三要素。

状态转移方程

状态转移方程是难点，思路：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

框架

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

斐波那契数列

暴力递归

int fib(int N) {
  if (N == 1 || N == 2) return 1;
  return fib(N-1) + fib(N-2)
}

递归树

eg ： n=20

流程： 计算原问题f（20），先计算出f（19）和f（18）；计算f（19）时要先计算f(18) 和 f(17)...

问题: 存在大量重复计算 （重叠子问题）

带备忘录的递归解法

创建一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

public static int fibonacci(int n) {
    if (n = 1) return1;
    if (n = 2) return2;
    if (map.get(n) != null)  {
        return map.get(n);
    }
    int result = fibonacci(n - 1) + fibonacci(n - 2);
    map.put(n, result);
    return result;
}

带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

自顶向下 - 由于不存在冗余计算，子问题为f(1), f(2), f(3) ... f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。

(动态规划是自底向上)

dp数组的迭代解法

改用自底向上的方式递推：

f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 5
....
f(n) = f(n-1) + f(n-2)

f(n) 就是定义的每个子问题的状态（DP 状态），f(n) = f(n-1) + f(n-2) 就是状态转移方程，即 f(n) 由 f(n-1), f(n-2) 这两个状态转移而来,由于每个子问题只与它前面的两个状态，所以我们只要定义三个变量，自底向上不断循环迭代即可

状态转移方程：f(n) 是一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移。

dp[i] = dp[i - 1] + dp[i - 2]

状态压缩 - 斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了

public int f(int n) {
    if (n == 1) return1;
    if (n == 2) return2;
    int result = 0;
    int pre = 1;
    int next = 2;
    
    for (int i = 3; i < n + 1; i ++) {
        result = pre + next;
        pre = next;
        next = result;
    }
    return result;
}

---

凑零钱问题

给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1

例如k=3, 面值为1，2，5；总金额为amount=11. 最少需要3枚硬币： 11 = 5 + 5 +1

思路： 把所有可能的凑硬币方法穷举出来，然后看最少需要多少硬币。

该问题是动态规划，因为有最优子结构，最优子结构： 子问题必须要互独立。

例如： 考试想考最高分，子问题就是语文，数学考到最高。为了考到最高，就要把语文考到最高，数学考到最高。另外没门课考到最高互相独立（不存在语文和数学分数相互制约）

凑零钱问题 ： 想知道amount=11时的最少硬币，如果知道怎么凑出amount=10的最少硬币数（子问题），只需要把子问题的答案再加1。另外硬币数量没有限制，因此子问题之间没有相互制约。

1. 递归

对于 amount 来说，如果我们选择了 coins 中的任何一枚硬币，则问题的规模(amount)是不是缩小了,再对缩小的 amount 也选择 coins 中的任何一枚硬币,直到再也不能选择（amount <= 0, amount = 0 代表有符合条件的解，小于0代表没有符合条件的解），从描述中我们可以看出问题可以分解成子问题，子问题与原问题具有相同的解决问题的思路，同时也有临界条件，符合递归的条件，由此可证可以用递归求解

定义函数

private static int f(int amount, int[] coins) {
}

递归公式

寻找问题与子问题的关系

假设 f(amount, coins) 为零钱 amount 的所需要的最少硬币数，当选中了coins 中的第一枚硬币之后（即为 coins[0]），则需再对剩余的 amount - coins[0] 金额求最少硬币数，即调用 f(amount - coins[0], coins) ,

选了第一枚硬币后的递推公式如下

f(amount, coins) = f(amount - coins[0]) + 1 (这里的 1 代表选择了第一枚硬币)

选择了第二，第三枚呢，递推公式如下

f(amount, coins) = f(amount-coins[1]) + 1 (这里的 1 代表选择了第二枚硬币)
f(amount, coins) = f(amount-coins[2]) + 1 (这里的 1 代表选择了第三枚硬币)

最终得到递推公式

f(amount, coins) = min{ f(amount - coins[i]) + 1) }, 其中 i 的取值为 0 到 coins 的大小，coins[i] 表示选择了此硬币, 1 表示选择了coins[i] 这一枚硬币

补全函数

public class Solution {

    private static int exchange(int amount, int[] coins) {

        // 说明零钱刚好凑完
        if (amount == 0) {
            return0;
        }

        // 说明没有满足的条件
        if (amount < 0) {
            return -1;
        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int subMin = exchange(amount - coins[i], coins);
            if (subMin == -1) continue;
            result = Math.min(subMin + 1, result);
        }

        // 说明没有符合问题的解
        if (result == Integer.MAX_VALUE) {
            return -1;
        }

        return result;
    }

    public static  void main(String[] args)  throws Throwable {
        int amount = 11;
        int[] coins = {1,2,5};
        int result = exchange(amount, coins);
        System.out.println("result = " + result);
    }
}

递归树分析

以amount=11 ，coins = {1,2,5}为例

2. 是否存在重叠子问题

上图中的 9， 8，都重复算了,所以存在重叠子问题

3. 使用备忘录（剪枝）

public class Solution {

    // 保存中间结果
    privatestatic HashMap<Integer, Integer> map = new HashMap();

    // 带备忘录的递归求解
    private static int exchangeRecursive(int amount, int[] coins) {
        if (map.get(amount) != null) {
            return map.get(amount);
        }
        // 说明零钱已经凑完
        if (amount == 0) {
            return0;
        }

        // 说明没有满足的条件
        if (amount < 0) {
            return -1;
        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int subMin = exchangeRecursive(amount - coins[i], coins);
            if (subMin == -1) continue;
            result = Math.min(subMin + 1, result);
        }

        // 说明没有符合问题的解
        if (result == Integer.MAX_VALUE) {
            return -1;
        }

        map.put(amount, result);
        return result;
    }

    public static  void main(String[] args)  throws Throwable {
        int amount = 11;
        int[] coins = {1,2,5};
        int result = exchangeRecursive(amount, coins);
        System.out.println("result = " + result);
    }
}

用自底向上的方式来递推，即动态规划

递推公式

f(amount, coins) = min{ f(amount - coins[i]) + 1) }, 其中 i 的取值为 0 到 coins 的大小，coins[i] 表示选择了此硬币, 1 表示选择了coins[i] 这一枚硬币

DP(i) 为凑够零钱 i 需要的最小值，状态转移方程如下

DP[i] = min{ DP[ i - coins[j] ] + 1 } = min{ DP[ i - coins[j] ]} + 1, 其中 j 的取值为 0 到 coins 的大小，1 代表取了 coins[j] 这一枚硬币。

我们只要自底向上根据以上状态转移方程依次求解 DP[1], DP[2],DP[3].,....DP[11]，最终的 DP[11]

private static int exchangeDP(int amount, int[] coins) {
    int[] dp = newint[amount + 1];
    // 初始化每个值为 amount+1，这样当最终求得的 dp[amount] 为 amount+1 时，说明问题无解
    for (int i = 0; i < amount + 1; i++) {
        dp[i] = amount + 1;
    }

    // 0 硬币本来就没有，所以设置成 0
    dp[0] = 0;

    for (int i = 0; i < amount + 1; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (i >= coins[j]) {
                dp[i] = Math.min(dp[i- coins[j]], dp[i]) + 1;
            }
        }
    }

    if (dp[amount] == amount + 1) {
        return -1;
    }
    return dp[amount];
}

参考

https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie

https://mp.weixin.qq.com/s/QPPTgPd0fucqnHjORnX4wA