关于动态规划，你想知道的都在这里了！
码农有道公众号
共 3016字，需浏览 7分钟
·
2020-12-17 02:03
来自公众号：AI科技大本营
作者：Your DevOps Guy
翻译：火火酱~，责编：晋兆
什么是动态规划？它又有什么重要的呢？
动态规划
最优子结构（Optimal substructure） 重叠子问题（Overlapping subproblems）
F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2)
要想解决一个大小为n的问题，我们可以调用相同的函数来解决同一问题的一个实例，但实例规模比原始问题规模小一些。 我们一直不断地调用该函数，直到到达基础用例，也就是停止条件，在此处即n = 0或n = 1。
递归和动态规划
多维（以及一维）数组——最常用的方法； 哈希表； 二叉搜索树；
如何解决动态规划问题
... ...的前n个元素； ... ...的所有方式； 有多少种... ...方式； 第n个... ... ； ... ...的最优解决方案； ... ...的最短小/最大/最短路径；
证明重叠子问题和次优结构特性。 定义子问题。 定义递归。 编写自上而下或自下而上的动态规划解决方案。
时间~子问题个数*每个子问题的时间
示例
一维问题
（1）斐波那契
int fib(int n) {
if (n == 0 || n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
}
检查我们需要的值是否已经在缓存中了。如果是，就返回它。 如果不是，就在返回之前先缓存的解决方案。
int fib(int n) {
vector<int> cache(n + 1, -1);
return fib_helper(n, cache);
}
int fib_helper(int n, vector<int> &cache) {
if(-1 != cache[n])
return cache[n];
if (n == 0 || n == 1)
cache[n] = 1;
else
cache[n] = fib_helper(n - 1, cache) + fib_helper(n - 2, cache);
return cache[n];
}
int fib(int n) {
vector<int> f(n + 1, 0);
f[1] = 1;
for(int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
int fib(int n) {
if (n == 0 || n == 1)
return 1;
//Variables that represent f(n - 1), f(n - 2) and f(n)
int n1= 1, n2 = 1, f = 0;
for (int i = 2; i <= n; i++) {
f= n1 + n2;
n2 = n1;
n1 = f;
}
return f;
}
几个变量，或许我们就可以摆脱一维数组，将其变成几个变量。 二维矩阵中的几行，或许我们可以将其减少成几个一维数组。 等等... ...
（2）爬楼梯
输入：2 输出：2 说明：有两种方法可以爬到顶端：1阶+1阶和2阶
输入：3 输出：3 说明：有三种方法可以爬到顶端：1阶+ 1阶+ 1阶，1阶+ 2阶，2阶+ 1阶
要得到f（N），就要先求出f（N-1）和 f（N-2）。 要得到f（N-1），就要先求出f（N-2）和 f（N-3）。 要得到f（N-2），就要先求出f（N-3）和 f（N-4）。
这个问题有重叠的子问题：你需要多次计算f（N-2）， f（N-3）， f（N-4），... ... 这个问题向我们展现了最优子结构：通过f（N-1）和f（N-2）的最优解，可以得到f（N）的最优解。
（3）最长递增子序列
迭代数组中的每一个元素，我们称其为X。 如果新元素Y大于X，那么序列可以扩展一个元素。 如果我们已经存储了所有子问题的解，那么获取新长度是非常简单的——只需在数组中进行查找即可。我们可以根据子问题的最优解得出新问题的解。 返回新的最长递增子序列的长度。
最优子结构：我们已经证明了大小为n的问题的最优解可以由子问题的最优解计算出来。 重叠子问题：要想计算s（n），则需要s（0）， s（1），... ...，s（n-1）。同样，要计算s（n-1），则需要s（0）， s（1），... ...，s（n-2）。同样的问题需要进行多次计算。
int lengthOfLIS(const vector<int>& nums) {
if(nums.empty())
return 0;
vector<int> dp(nums.size(), 1);
int maxSol = 1;
for(int i = 0; i < nums.size(); ++i){
for(int j = 0; j < i; ++j){
if(nums[i] > nums[j]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxSol = max(maxSol, dp[i]);
}
return maxSol;
}
（4）有多少BST
输入：5 输出：42 说明：给定n = 5, 总共有42个唯一的BST
3是根 3的左边是数字1和2 3的右边是数字4和5
选一个元素作为BST的根； 解决（1到根-1）和（根+1到n）两个数字的相同问题； 将每个子问题的两个结果相乘； 将其加到我们的运行总计上； 继续下一个根；
int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; ++i){
for(int j = 0; j < i; ++j){
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp.back();
}
二维问题
自上而下的解决方案和之前没有太大的区别：找到递归并使用缓存。 对于自下而上的解决方案，一个2D数组就足以存储结果了。像我之前提到的，可能会减少一个或几个一维数组，但是没有必要太在意。之所以提到这一点只是以防你在解决问题时看到会有点摸不着头脑。
（1）最小路径和
输入：[ [1,3,1], [1,5,1], [4,2,1] ] 输出：7 说明：因为路径1→3→1→1→1总和最小
int minPathSum(const vector<vector<int>>& grid) {
const int nrow = grid.size();
if(nrow == 0)
return 0;
const int ncol = grid[0].size();
vector<vector<int>> minSum(nrow, vector<int>(ncol, 0));
minSum[0][0] = grid[0][0];
for(int col = 1; col < ncol; ++col)
minSum[0][col] = minSum[0][col - 1] + grid[0][col];
for(int row = 1; row < nrow; ++row)
minSum[row][0] = minSum[row - 1][0] + grid[row][0];
for(int col = 1; col < ncol; ++col){
for(int row = 1; row < nrow; ++row){
minSum[row][col] = min(minSum[row - 1][col], minSum[row][col - 1]) + grid[row][col];
}
}
return minSum[nrow - 1][ncol - 1];
}
（2）背包问题
我们可以把这样物品放到背包里（如果合适的话)，背包的总价值增加，容量减少。 我们可以放弃这样物品，背包里的价值和容量不变。
// Recursive. Try to turn this into a piece of top-down DP code.int knapSack(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
}
// C style, in case you are not familiar with C++ vectorsint knapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max( val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
（3）最长公共子序列
输入：text 1 = “abcde”, text 2 = “ace” 输出：3 说明：最长公共子序列是 “ace” ，且其长度为3
如果相等，那么LCS的长度至少为1。我们需要调用f(A[0:n-1]， B[0:n-1])来查找该索引前的LCS，并加1，因为A[n]和B[n]是相同的。 如果不相等，我们就删除两个字符串的最后一个字符——一次删一个，并查找生成LCS的路径。换句话说，我们取f(A[0: n-1]， B)和f(A, B[0:n-1])的最大值。 重叠子问题：我们来看看可能会出现的调用：(“abcde”, “ace”)产生x1 = (“abcd”, “ace”)和y1 = (“abcde”, “ac”)；x1将产生x12 = (“abc”, “ace”) 和y12= (“abcd”, “ac”)；y1将产生(“abcd”, “ac”)和(“abcde”, “a”)。如你所见，同样的问题需要计算很多次。 最优子结构：与最长递增子序列非常类似。如果我们在其中一个字符串A’中添加一个额外的字符，就可以从所有的缓存结果中快速计算出解决方案，而这些结果是我们解A和B得到的。
int longestCommonSubsequence(const string &text1, const string &text2) {
const int n = text1.length();
const int m = text2.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1,0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(text1[i-1] == text2[j-1])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}
总结
原文链接：
https://hackernoon.com/all-you-need-to-know-about-dynamic-programming-0tj3e5l
本文由AI科技大本营翻译，转载请注明出处
推荐阅读：
专注服务器后台技术栈知识总结分享
欢迎关注交流共同进步
评论