教育网站制作视频,关于网站建设的新闻,注册一个家政公司需要多少钱,做视频网站都需要什么爬楼梯(plus) 一步一个台阶#xff0c;两个台阶#xff0c;三个台阶#xff0c;…#xff0c;直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢#xff1f; 1阶#xff0c;2阶#xff0c;… m阶就是物品#xff0c;楼顶就是背包。每一阶可以重复使用#xff0c;例如…爬楼梯(plus) 一步一个台阶两个台阶三个台阶…直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢 1阶2阶… m阶就是物品楼顶就是背包。每一阶可以重复使用例如跳了1阶还可以继续跳1阶。问跳到楼顶有几种方法其实就是问装满背包有几种方法。此时大家应该发现这就是一个完全背包问题了 确定dp数组以及下标的含义:dp[i]爬到有i个台阶的楼顶有dp[i]种方法。 确定递推公式:那么递推公式为dp[i] dp[i - j] dp数组如何初始化既然递归公式是 dp[i] dp[i - j]那么dp[0] 一定为1dp[0]是递归中一切数值的基础所在如果dp[0]是0的话其他数值都是0了。 确定遍历顺序这是背包里求排列问题先背包后物品。 Int clam(int m,int n){//n表示楼层高度m表示步数选择1到mVectorint dp(n1,0);Dp[0]1;For(int i0;in;i){For(int j1;im;j){If(i-j0){Dp[i]dp[i-j];}}}Return dp[n];
}时间复杂度: O(nm)空间复杂度: O(n)
题目零钱兑换 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。你可以认为每种硬币的数量是无限的。 题目中说每种硬币的数量是无限的可以看出是典型的完全背包问题。 确定dp数组以及下标的含义dp[j]凑足总额为j所需钱币的最少个数为dp[j]确定递推公式凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i]所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);dp数组如何初始化首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。确定遍历顺序本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。所以先背包或先物品对结果没影响。 class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount1,INT_MAX);dp[0]0;for(int i0;iamount;i){for(int j0;jcoins.size();j){if(i-coins[j]0 dp[i-coins[j]]!INT_MAX){dp[i] min(dp[i],dp[i-coins[j]]1);}}}return dp[amount]INT_MAX?-1:dp[amount];}
};时间复杂度: O(n * amount)其中 n 为 coins 的长度空间复杂度: O(amount)
题目完全平方数 给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 确定dp数组dp table以及下标的含义dp[j]和为j的完全平方数的最少数量为dp[j] 确定递推公式dp[j] 可以由dp[j - i * i]推出 dp[j - i * i] 1 便可以凑成dp[j]。此时我们要选择最小的dp[j]所以递推公式dp[j] min(dp[j - i * i] 1, dp[j]); dp数组如何初始化dp[0]表示 和为0的完全平方数的最小数量那么dp[0]一定是0。从递归公式dp[j] min(dp[j - i * i] 1, dp[j]);中可以看出每次dp[j]都要选最小的所以非0下标的dp[j]一定要初始为最大值这样dp[j]在递推的时候才不会被初始值覆盖。 class Solution {
public:int numSquares(int n) {vectorint dp(n1,INT_MAX);dp[0]0;for(int i0;in;i){for(int j1;j*ji;j){dp[i] min(dp[i],dp[i-j*j]1);}}return dp[n];}
};题目单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。**注意**不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词说明就是一个完全背包 确定dp数组以及下标的含义dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。确定递推公式如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。dp数组如何初始化从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。确定遍历顺序本题其实我们求的是排列数为什么呢。 拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例。“apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。所以说本题一定是 先遍历 背包再遍历物品。 class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordset(wordDict.begin(),wordDict.end());vectorbool dp(s.size()1,false);dp[0]true;for(int i1;is.size();i){for(int j0;ji;j){string words.substr(j,i-j);//substr(起始位置截取的个数)if(wordset.find(word)!wordset.end() dp[j]){dp[i]true;}} }return dp[s.size()];}
};时间复杂度O(n^3)因为substr返回子串的副本是O(n)的复杂度这里的n是substring的长度空间复杂度O(n)
多重背包
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。
题目打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。所以这里就更感觉到当前状态和前面状态会有一种依赖关系那么这种依赖关系都是动规的递推公式。当然以上是大概思路打家劫舍是dp解决的经典问题接下来我们来动规五部曲分析如下 确定dp数组dp table以及下标的含义如果偷第i房间那么dp[i] dp[i - 2] nums[i] 即第i-1房一定是不考虑的找出 下标i-2包括i-2以内的房屋最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间那么dp[i] dp[i - 1]即考 虑i-1房注意这里是考虑并不是一定要偷i-1房这是很多同学容易混淆的点。然后dp[i]取最大值即dp[i] max(dp[i - 2] nums[i], dp[i - 1]);dp数组如何初始化从递推公式dp[i] max(dp[i - 2] nums[i], dp[i - 1]);可以看出递推公式的基础就是dp[0] 和 dp[1]从dp[i]的定义上来讲dp[0] 一定是 nums[0]dp[1]就是nums[0]和nums[1]的最大值即dp[1] max(nums[0], nums[1]); class Solution {
public:int rob(vectorint nums) {if(nums.size()0){return 0;}if(nums.size()1){return nums[0];}vectorint dp(nums.size());dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(int i2;inums.size();i){dp[i]max(dp[i-2]nums[i],dp[i-1]);}return dp[nums.size()-1];}
};时间复杂度: O(n)空间复杂度: O(n)
题目打家劫舍 II 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 class Solution {
public:int robpart(vectorint numspart,int start,int end){if(endstart) return numspart[start];vectorint dp(numspart.size());dp[start] numspart[start];dp[start1] max(numspart[start],numspart[start1]);for(int istart2;iend;i){dp[i] max(dp[i-2]numspart[i],dp[i-1]);// coutdp[i] ;}return dp[end];}int rob(vectorint nums) {if(nums.size()0){return 0;}if(nums.size()1){return nums[0];}int left robpart(nums,0,nums.size()-2);// coutendl;int right robpart(nums,1,nums.size()-1);// coutleft rightendl;// return leftright?left:right;return max(left,right);}
};题目打家劫舍 III 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。 这道题目算是树形dp的入门题目因为是在树上进行状态转移在讲解二叉树的时候说过递归三部曲那么下面我以递归三部曲为框架其中融合动规五部曲的内容来进行讲解。 确定递归函数的参数和返回值要求一个节点 偷与不偷的两个状态所得到的金钱那么返回值就是一个长度为2的数组。所以dp数组dp table以及下标的含义下标为0记录不偷该节点所得到的的最大金钱下标为1记录偷该节点所得到的的最大金钱。确定终止条件在遍历的过程中如果遇到空节点的话很明显无论偷还是不偷都是0所以就返回确定遍历顺序首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。通过递归左节点得到左节点偷与不偷的金钱。通过递归右节点得到右节点偷与不偷的金钱。确定单层递归的逻辑如果是偷当前节点那么左右孩子就不能偷val1 cur-val left[0] right[0]; 如果不偷当前节点那么左右孩子就可以偷至于到底偷不偷一定是选一个最大的所以val2 max(left[0], left[1]) max(right[0], right[1]);最后当前节点的状态就是{val2, val1}; 即{不偷当前节点得到的最大金钱偷当前节点得到的最大金钱} /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint robtree(TreeNode *cur){if(curnullptr){return vectorint{0,0};}vectorint leftrobtree(cur-left);vectorint rightrobtree(cur-right);int val1cur-valleft[0]right[0];int val2max(left[0],left[1])max(right[0],right[1]);return {val2,val1};}int rob(TreeNode* root) {vectorint resrobtree(root);return max(res[0],res[1]);}
};时间复杂度O(n)每个节点只遍历了一次空间复杂度O(log n)算上递推系统栈的空间
