本文主要是介绍重拾C++之菜鸟刷算法第16篇 --- 动态规划(总结篇),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
动态规划
五部曲
- 确定dp数组的含义
- 递推公式
- 正确进行初始化
- 遍历顺序
- 举例推到dp数组
01 背包问题
第一种:填满背包所需的最大价值
有n件物品和一个最多可以背重量为w的背包。第i件物品的重量是weight[i],得到的价值是value[i],所有物品只能使用一次。
滚动数组解法
-
首先确定dp数组含义:dp[j] 表示 容量为 j 的背包能背的最大价值是 dp[j]
-
确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
只有两种情况
- 第一种是当物品i的重量大于背包j的重量,物品i无法放入背包,因此背包的价值依然和前面相同
- 第二种是因为dp[j - weight[i]]表示 j - weight[i] 重量的时候,此时最大的价值,那么dp[j - weight[i]] + value[i] 表示此时的背包放入物品i得到的最大价值
-
初始化:背包容量为0的话,其价值也为0,因此dp[i] = 0
-
遍历顺序:先遍历物品数量,再从背包容量倒序遍历,防止物品重复使用
-
举例说明dp数组
416. 分割等和子集 - 力扣(LeetCode)
1049. 最后一块石头的重量 II - 力扣(LeetCode)
第二种:装满容量为x的背包,有几种方法
-
首先确定dp数组含义:dp[j] 表示 容量为 j 的背包有 dp[j] 种方法
-
确定递推公式:dp[j] += dp[j - weight[i]] (组合类问题)
-
初始化:背包容量为0的话,其价值也为0,因此dp[i] = 0
-
遍历顺序:先遍历物品数量,再从背包容量倒序遍历,防止物品重复使用
-
举例说明dp数组
494. 目标和 - 力扣(LeetCode)
474. 一和零 - 力扣(LeetCode)
完全背包
与01背包唯一不同的地方是,每种物品有无限件
-
首先确定dp数组含义:dp[j] 表示 容量为 j 的背包能背的最大价值是 dp[j]
-
确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
只有两种情况
- 第一种是当物品i的重量大于背包j的重量,物品i无法放入背包,因此背包的价值依然和前面相同
- 第二种是因为dp[j - weight[i]]表示 j - weight[i] 重量的时候,此时最大的价值,那么dp[j - weight[i]] + value[i] 表示此时的背包放入物品i得到的最大价值
-
初始化:背包容量为0的话,其价值也为0,因此dp[i] = 0
-
遍历顺序:先遍历物品数量,再从小到大遍历背包容量(i那位完全背包的物品是可以添加多次的)
-
举例说明dp数组
518. 零钱兑换 II - 力扣(LeetCode)
377. 组合总和 Ⅳ - 力扣(LeetCode)
这篇关于重拾C++之菜鸟刷算法第16篇 --- 动态规划(总结篇)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!