动态规划解题套路框架

[TOC] ## 概述 - 首先，动态规划问题的一般形式就是求最值 - 求解动态规划的核心问题是穷举 - 动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算 - 动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值 - 正确的「状态转移方程」才能正确地穷举 写出状态转移方程是最困难的，状态转移方程思考 `明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义` ## 斐波那契数列 ### 暴力递归 ``` int fib(int N) { if (N == 1 || N == 2) return 1; return fib(N - 1) + fib(N - 2); } ``` 假设值为20 ,则如图效率非常的低  递归算法的时间复杂度怎么计算？ - 就是用子问题个数乘以解决一个子问题需要的时间。 - 首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。 然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。 所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸 算法低效的原因? - 存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。 这就是动态规划问题的第一个性质：重叠子问题 ### 带备忘录的递归解法 ``` func fib(n int) int { if n <= 2 { return 1 } mem := make([]int, n, n) return helper(n, mem) } func helper(n int, men []int) int { if n <= 2 { return 1 } if i := men[n-1]; i != 0 { return i } men[n-1] = helper(n-1, men) + helper(n-2, men) return men[n-1] } ```  带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数  时间复杂度 - 即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) ... f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。 解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。 所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击 ### dp 数组的迭代解法 ``` int fib(int N) { vector dp(N + 1, 0); // base case dp[1] = dp[2] = 1; for (int i = 3; i <= N; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[N]; } ```  「状态转移方程」  你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移