动态规划文章目录动态规划01背包多重背包分组背包区间dp洛谷例题camp训练赛牛客竞赛网两个约束条件最优子结构：为了计算考虑了前i个物品，总体积为j时的最大收益，我们可以先计算考虑了前i-1个物品，总体积为j时的最大收益以及考虑了前i-1个物品，总体积为时的最大收益。知道了考虑了前i-1个物品，总体积为j时的最大收益以及考虑了前i-1个物品，总体积为时的最大收益，我们就能算出考虑了前i个物品，总体积为j时的最大收益。由于在每次拆解过程中我们会少考虑1个物品，最后一定会在有限次拆解后变成一个什么物品都不考虑的子问题，所以在问题拆解过程中不会陷入无限递归。**无后效性：**我们只关心考虑了前i个物

1.0/1背包1.1.算法思路0/1背包是动态规划、背包问题中最经典的问题啦！它主要的问题是：给定n种物品、这n种物品的重量分别是，价值分别是 ，而你有一个容量为C的背包，请问如何求出所能拿的最大价值呢？对于动态规划，我们先需要找到一条推导公式，然后确定边界：我们设dp[i][j]为一个背包，表示前i个物品装入容器为j的背包中可以获得的最大价值。我们可以推导出：dp[i][j]=max(dp[i-1][j],dp[i-1][j- ]+ )也就是说，当前的dp值由装和不装入第i个物品来决定的。不装入第i个是：dp[i-1][j]，装入的话j要减去这个物品的重量也就是： dp[i-1][j- ]+

目录🌟一、了解动态规划DP🌟二、闫式DP分析法🌟三、01背包[DP入门]一维写法[优化：对代码等价变形]终极版本🌟四、完全背包🌟五、多重背包朴素做法优化🌟六、分组背包问题🌟七、个人总结01背包&完全背包多重背包&多组背包🌟八、文章参考🌟九、最后前言欢迎关注我的专栏,准备写完算法基础所有题解🚀🚀🚀专栏链接🌟一、了解动态规划DP指的是将一个复杂的问题，分解成简单的问题（用一种递归的方式）——WIKI本质：分治（与递归没有本质区别）+最优解，很多就是一些细节的不同。🌟二、闫式DP分析法y总的方法🌟三、01背包[DP入门][0-1]背包最基础动态规划，也是所以背包问题的基础，特点是：每种物品仅有一件，

问题背景有N件物品和⼀个最多能背重量为W的背包。第i件物品的重量是weight[i]，价值是value[i]。每件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥所得物品价值总和最⼤。二维dp分析1.确定dp(dptable)数组及其下标的含义dp[i][j]：在下标为[0,i]的物品任意选取，放进容量为j的背包中，所的物品的最大价值为dp[i][j]。2.确定递推公式我们从第0件物品开始遍历，逐个确定要不要将第i件物品放入背包，这当然要综合考虑物品的重量以及价值。假设此时我们遍历到第i件物品，此时有两种情况。第一种：此时背包容量jj，第i件物品的重量超过了背包容量本身，那么肯定不能将第i件物品放入背

力扣题目：01背包问题（二维数组）刷题时长：参考题解解题方法：动态规划+ 二维dp数组复杂度分析时间空间问题总结理解递推公式困难本题收获动规思路：两层for循环，第一层i遍历物品，第二层j枚举背包容量以内所有值确定dp数组及下标的含义：dp[i][j]表示从下标为[0-i]的物品范围中任意取，放进容量为j的背包后价值总和的最大值确定递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])当背包容量小于物品重量，不放物品，此时价值总和为dp[i-1][j]。即当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然

对于动态规划问题，就是牺牲空间来提高时间，通过将一个个小问题的答案存储起来，直接供给后面问题求解，避免重复的运算，从而提高效率，这就是动态规划的思想。下面我们通过一个经典的01背包问题来了解动态规划的解题方法吧（文末附上完整代码）首先，将每个物品的体积以及价值存放在列表中，代码和运行结果如下： 可以看到，我们将三个物品信息放入列表中，第一个元素用[0,0]占位，使列表下标就是物品对应的序号，便于我们对代码的理解。接下来我们将列表arr和背包容量bag传入函数进行运算，函数代码如下：首先创建一个列表value，一共(bag+1)列，len(arr)行，先全部填充为0背包容量物品012345000

139.单词拆分给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。示例1：输入:s="leetcode",wordDict=["leet","code"]输出:true解释:返回true因为"leetcode"可以由"leet"和"code"拼接成。示例2：输入:s="applepenapple",wordDict=["apple","pen"]输出:true解释:返回true因为"applepenapple"可以由"apple""pen""apple"拼接成

文章目录前言动态规划的维度二维动规leetcode416、分割等和子集leetcode1049.最后一块石头的重量IIleetcode494、目标和三维动规leetcode474.一和零结语前言大家好久不见，这次我们一起来学习一下动态规划中怎么确定维度，和对应问题如何解决。动态规划的维度一个维度：只有物品两个维度：物品和容量三个维度：物品和容量1和容量2之前讲解动态规划问题时，斐波那契数列就是一个很简单的一维动态规划问题，因为我们要考虑的状态只有这个数的值，（一维动态规划），之后讲解了01背包问题，也就是有了第二个维度，不仅要考虑物品，还要考虑背包容量（二维动态规划）其实在这里一定要明确好状态

算法套路十四——动态规划之背包问题：01背包、完全背包及各种变形如果对递归、记忆化搜索及动态规划的概念与关系不太理解，可以前往阅读算法套路十三——动态规划DP入门背包DP介绍：https://oi-wiki.org/dp/knapsack/算法示例一——0/1背包：0-1背包:有n个物品，第i个物品的体积为w[i]，价值为v[i]，每个物品至多选一个，求体积和不超过capacity时的最大价值和，其中i从0开始。递归+记忆化搜索递归函数定义：在0/1背包问题中，递归函数dfs需要2个参数，i和c来表示当前考虑的物品和背包的剩余容量，dfs(i,c)代表的是考虑前i个物品，在背包容量为c的情况下

动态规划part08139.单词拆分题目描述思路回溯法背包问题拓展关于多重背包多重背包总结背包问题总结篇背包递推公式遍历顺序01背包完全背包总结139.单词拆分题目链接：139.单词拆分参考：https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html题目描述给定一个非空字符串s和一个包含非空单词的列表wordDict，判定s是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例1：输入:s=“leetcode”,wordDict=[“le