专营网站建设,中文网站建设小组,电子商务网站建设维护,知名网建公司学习目标#xff1a; 动态规划五部曲#xff1a; ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录#xff01; 本文大多数内容引用自代码随想录 60天训练营打卡计划#xff01;
学习内容#xff1a; …学习目标 动态规划五部曲 ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录 本文大多数内容引用自代码随想录 60天训练营打卡计划
学习内容 上述内容引用自代码随想录
使用动归五部曲分析题目见过的题目就可以被轻松带走。最重要的就是dp[]数组的含义递归函数即遍历的顺序。
1.背包递推公式
问能否能装满背包或者最多装多少 dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 对应题目如下
动态规划416.分割等和子集动态规划1049.最后一块石头的重量 II动态规划139.单词拆分
问装满背包有几种方法dp[j] dp[j - nums[i]] 对应题目如下
动态规划494.目标和动态规划518. 零钱兑换 II动态规划377.组合总和Ⅳ动态规划70. 爬楼梯进阶版完全背包
问背包装满最大价值 dp[j] max(dp[j], dp[j - weight[i]] value[i]); 对应题目如下
动态规划474.一和零
问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j]); 对应题目如下
动态规划322.零钱兑换动态规划279.完全平方数
2.遍历顺序
01背包
二维dp数组01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。一维dp数组01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历。
完全背包
说完01背包再看看完全背包。
一维dp数组实现先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。但是仅仅是纯完全背包的遍历顺序是这样的题目稍有变化两个for循环的先后顺序就不一样了。
如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。
相关题目如下
求组合数
动态规划518.零钱兑换II
求排列数
动态规划377. 组合总和 Ⅳ动态规划70. 爬楼梯进阶版完全背包
如果求最小数那么两层for循环的先后顺序就无所谓了相关题目如下 求最小数
动态规划322. 零钱兑换动态规划279.完全平方数
对于背包问题其实递推公式算是容易的难是难在遍历顺序上如果把遍历顺序搞透才算是真正理解了。 学习时间
上午两个半小时整理文档半小时。
