关于动态规划,你想知道的都在这里了!
码农有道公众号
共 3016字,需浏览 7分钟
· 2020-12-17
来自公众号:AI科技大本营
作者:Your DevOps Guy
翻译:火火酱~,责编:晋兆
什么是动态规划?它又有什么重要的呢?
动态规划
最优子结构(Optimal substructure) 重叠子问题(Overlapping subproblems)
F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2)
![](https://filescdn.proginn.com/a1d19cff86b574e21bbbbbb7ec114e74/3d0f45002e9ba8eaf1cb3a7ee92c5ab1.webp)
要想解决一个大小为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科技大本营翻译,转载请注明出处
推荐阅读:
专注服务器后台技术栈知识总结分享
欢迎关注交流共同进步
评论