代码编织梦想

完全背包问题】完全背包问题是指不限制物品的数量,可以无限制取物品。而 01 背包问题是每个物品只能取一次。
求放满背包共有几种方法】:

  1. 递推公式:一般都是 dp[j] += dp[j - weight[i]]
  2. 遍历顺序:
    1)当求放满的组合共有几种不考虑子集顺序时:先遍历物品后遍历背包(背包正序遍历);
    2)当求放满的排列共有几种考虑子集顺序时,要先遍历背包后遍历物品;
    3)如果只是求能否放满背包不求几种方法时就哪种遍历顺序都可以。
  • 518. 零钱兑换 II
    思路】这道题属于求放满背包有几种组合(不考虑子集顺序),就用先遍历物品后遍历背包的顺序。

    var change = function(amount, coins) {
      let dp = new Array(amount + 1).fill(0);
      dp[0] = 1;
      for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
          dp[j] += dp[j - coins[i]];
        }
      }
      return dp[amount];
    };
    
  • 377. 组合总和 Ⅳ
    思路】这道题属于放满背包求几种排列(考虑子集排序)。

    var combinationSum4 = function(nums, target) {
      let dp = new Array(target + 1).fill(0);
      dp[0] = 1;
    
      // 求排列要先遍历背包后遍历物品
      for (let i = 0; i <= target; i++) {
        for (let j = 0; j < nums.length; j++) {
          if(i >= nums[j]) dp[i] += dp[i - nums[j]];
        }
      }
      return dp[target];
    };
    

参考代码随想录:https://www.programmercarl.com/

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44473700/article/details/128019439

leetcode 刷题 log day2_音音子-的博客-爱代码爱编程

977. 有序数组的平方 【思路】重点在于怎么判断负数平方后的位置,负数越小,平方后的值就越大,平方后的最大值只能存在于数组两端,不可能在中间,所以利用双指针,一首一尾,若当前指针所指的数的平方较大时,指针后移(前移)一位

leetcode 刷题 log day22_音音子-的博客-爱代码爱编程

235. 二叉搜索树的最近公共祖先 【思路】难点和重点在于思考怎么利用搜素二叉树的性质得到最近的公共祖先:如果p 和 q 各在一个节点的左子树和右子树,那么这个节点就是最近的公共祖先。 // 递归 从根节点开始遍历,找到

leetcode刷题 log day23_音音子-的博客-爱代码爱编程

669. 修剪二叉搜索树 【思路】这道题和删除二叉树节点的题目类似,看似删除二叉树节点只删除一个节点,比这道比较区间的题简单,但是思考后发现,比较区间的情况比删除单个节点的情况简单,因为删除一个节点要考虑该节点的左子树和右

leetcode 刷题 log day24_音音子-的博客-爱代码爱编程

回溯算法 什么是回溯: 回溯是一种搜索方式,纯暴力搜索,有递归就会有回溯,解决了 for 循环嵌套解决不了的问题。本质就是穷举法,所以效率不会很高,虽然可以途中使用剪枝的技巧,但本质就是穷举所有选项,筛选我们想要的结果。

leetcode 刷题 log day 30_音音子-的博客-爱代码爱编程

先恭喜恭喜自己! 🎉🎉🎉🎉🎉🎉🎉🎉🎉 一个月噜!(晚餐还奖励了自己芒果糯米饭!椰香咖喱牛腩,还想吃椰子冻,结果卖没了,害! 今天有点忙,而且题目也费时间,所以只做了一道(哭泣),但是把业务代码敲完了! 332.重新安排行

leetcode 刷题 log day 31_音音子-的博客-爱代码爱编程

【贪心算法】没什么规律和模板,一般思想是从局部最优推出全局最优。 455. 分发饼干 【思路】先想局部最优:最小的饼干喂给胃口最小的小孩,或最大的饼干喂给满足条件的胃口最大的小孩,就可以推出全局最优:满足数量最多的孩子。

leetcode 刷题 log day 32_音音子-的博客-爱代码爱编程

122. 买卖股票的最佳时机 || 【思路】按照局部最优推出全局最优的思路。局部最优是获得最小买卖单位内的最大利润,就可以在全局最优获得最小买卖单位的最大利润。即当股票价格递增时,就买入第二天卖出。每天对股票进行操作。 v

leetcode 刷题 log day 34_音音子-的博客-爱代码爱编程

1005. K次取反后最大化的数组和 【思路】要最后数组的和最大,那么就要取反后的数值最大,那么就要判断负数和正数,正负数越小的取反,就可以按照绝对值的大小排列然后负数的取反,遇到有 0 的就都取0,当把所有的负数都变为正

leetcode 刷题 log day 37_音音子-的博客-爱代码爱编程

738. 单调递增的数字 【思路】感觉遇到这种题目,乍一眼看上去不知道怎么做,就得先试,先想怎么才能找到符合条件的最大值,发现是前一位减一,当前位变为 9 就是最大值,找到规律之后就是写代码了,从前遍历还是从后遍历呢,没有

leetcode 刷题 log day 39_音音子-的博客-爱代码爱编程

62. 不同路径 【思路】画图找规律哈哈哈哈哈,真的对于动态规划好管用!! var uniquePaths = function(m, n) { let dp = new Array(m).fill().map(i

leetcode 刷题 log day 41_音音子-的博客-爱代码爱编程

343. 整数拆分 【思路】好像除了找规律三个字写不出第二句话哈哈哈哈。累了,就这样吧,祝愿自己下次推导还会 🙏 var integerBreak = function(n) { let dp = new Array(

leetcode 刷题 log day 43_音音子-的博客-爱代码爱编程

1049. 最后一块石头的重量 II 【思路】这道题的难点在于怎么和背包问题扯上关系。从数组中任意选两个元素,粉碎石头添加剩余的量,直到剩余的重量最小,就可以把石头尽可能的重量平均分成两堆,子集之和相减,留下的就是最小的重

leetcode 刷题 log day 45_音音子-的博客-爱代码爱编程

70. 爬楼梯 (进阶) 【思路】要上的台阶数就是背包容量,每次只能上一个台阶或者两个台阶,就是物品的值。因为要考虑排列顺序,所以先遍历背包后遍历物品,分析完毕套公式~ // 斐波那契做法 var climbStairs

leetcode 刷题 log day 25-爱代码爱编程

216. 组合总和 III 【思路】相比于上一道求组和的题,多了一个判断条件:和,所以要在判断 k 的时候加上判断和是否相等。 var combinationSum3 = function(k, n) { let

leetcode刷题log day17-爱代码爱编程

【知识点总结】如果是模拟前中后序遍历就用栈,如果是适合层序遍历就用队列。 110. 平衡二叉树 【思路】比较高度,要从子节点开始比较,所以使用后序遍历。如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢?可以用其左

leetcode 刷题 log day21-爱代码爱编程

【解题技巧】凡是求二叉树中的一个值(最大值 or 最小值 or 求和)之类的,都可以先设定一个初始值,遍历的同时进行比较覆盖,把值实时记录下来,等遍历完,就可以得到我们想求的值,和双指针法结合起来一起用可达到事半功倍的效果。

leetcode刷题 log day 28-爱代码爱编程

【感悟】写题越来越快啦,而且可以自己写出来了,每天努力一点点,真的可以慢慢变厉害!希望看到我的 blog 的有缘人也可以努力,真的没有想象中的难! 93.复原IP地址 【思路】这道题的重点在于在哪加 . ,递归的起始位置

leetcode 刷题 log day 29_letcode log-爱代码爱编程

【总结】判断是否重复的两种方法: 1. 题目不要求顺序:使用 used 数组记录是否遍历过元素相同的值 2. 题目对顺序有要求:创建 set 实例,记录每一个遍历过的元素的值,每次遍历之前判断是否已经遍历过相同的值(这种方法

leetcode 刷题 log day 42-爱代码爱编程

【标准的背包问题】有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 eg:weight = [1,