关于动态规划,你想知道的都在这里了!
码农有道公众号
共 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)
要想解决一个大小为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科技大本营翻译,转载请注明出处
推荐阅读:
专注服务器后台技术栈知识总结分享
欢迎关注交流共同进步
评论
盘点Lombok的几个骚操作,你绝对没用过!
👉 欢迎加入小哈的星球 ,你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利全栈前后端分离博客项目 2.0 版本完结啦, 演示链接:http://116.62.199.48/ ,新项目正在酝酿中
小哈学Java
0
堪称最优秀的Docker可视化管理工具——Portainer你真的会用吗?
来源:blog.csdn.net/shark_chili3007/article/details/123366179👉 欢迎加入小哈的星球 ,你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利全栈前后端分离博客项目
小哈学Java
0
如何计算数据中心的冷却需求?
今日分享 【导读】数据中心的冷却要求受多种因素影响,包括设备的热量输出、占地面积、设施设计和电气系统功率额定值等等……众所周知,环境因素会严重影响数据中心设备。过多的热量积聚会损坏服务器,可能导致其自动关闭。经常在高于可接受的温度下运行服务器会缩短其使用
数据中心运维管理
0
多人同时导出 Excel 干崩服务器!新来的阿里大佬给出的解决方案太优雅了!
点击关注公众号,Java 干货及时推送↓推荐阅读:面试辅导,我们出大成果了!来源:juejin.cn/post/7259249904777838629前言 业务诉求:考虑到数据库数据日渐增多,导出会有全量数据的导出,多人同时导出可以会对服务性能造成影响,导出涉及到mysql查询的io操作,
Java技术栈
1
今年后端爆了???
大家好,我是二哥呀。每次登录牛客,看到最多的就是各种 Java 后端岗位的喜讯,美团 OC了、快手 OC 了、就连腾讯 OC 的都是 Java 岗,我怀疑牛客是不是给我打了“只报喜不报忧”的标签?星球里也有不少球友给我发来喜讯,难道说每年都在凉凉的 Java 后端又承担起了就业的重任?!不可能,绝对
沉默王二
3
什么样的冷却方法适合数据中心运营?
冷却数据中心的最简单方法是安装空气交换器,通过服务器室生成冷空气。但是,如果想要节省资金,至少从长远来看,更好的方法可能是在每个机架上安装空气交换器,并使用它们为单个机架的服务器降温。"后机架冷却",与数据中心中更为传统的空气冷却系统相比,特别是在能源效率方面,其具有一些优势。冷却数据中心的最简单
数据中心运维管理
0
大厂都在用的 Git 代码管理规范 !
👉 欢迎加入小哈的星球 ,你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利全栈前后端分离博客项目 2.0 版本完结啦, 演示链接:http://116.62.199.48/ ,新项目正在酝酿中
小哈学Java
2
Go 1.22 的新增功能系列之二:reflect.TypeFor
Go 1.22 的第一个候选版本已经发布,这意味着最终版本即将发布,现在是我在博客中介绍我在这个周期中所做工作的时候了。像往常一样,我的贡献很小,但它们是我的,所以我将从幕后的角度来谈谈它们。首先是reflect.TypeFor。这是整个函数:// TypeFor returns the [Type
GoCN
0