通知短信+运营短信,5秒速达,支持群发助手一键发送🚀高效触达和通知客户 广告
[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 ,则如图效率非常的低 ![](../../../images/screenshot_1603889903089.png) 递归算法的时间复杂度怎么计算? - 就是用子问题个数乘以解决一个子问题需要的时间。 - 首先计算子问题个数,即递归树中节点的总数。显然二叉树节点总数为指数级别,所以子问题个数为 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] } ``` ![](../../../images/screenshot_1603890529709.png) 带「备忘录」的递归算法,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数 ![](../../../images/screenshot_1603890561519.png) 时间复杂度 - 即图中节点的总数,由于本算法不存在冗余计算,子问题就是 f(1), f(2), f(3) ... f(20),数量和输入规模 n = 20 成正比,所以子问题个数为 O(n)。 解决一个子问题的时间,同上,没有什么循环,时间为 O(1)。 所以,本算法的时间复杂度是 O(n)。比起暴力算法,是降维打击 ### dp 数组的迭代解法 ``` int fib(int N) { vector<int> 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]; } ``` ![](https://img.kancloud.cn/3b/3b/3b3bf4b680d43e5ef33bb2516a9553c1_1280x720.png) 「状态转移方程」 ![](https://img.kancloud.cn/13/a7/13a72c6a8a44b4711f3166355d1f912d_464x97.png) 你把 f(n) 想做一个状态 n,这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来,这就叫状态转移