2024-12-06
1.7k 字
6 分钟
动态规划-01背包理论基础(二)
动态规划-01背包理论基础(二)
上一篇我们提到了01背包的二维的dp数组，这篇我们就来说一说01背包的一维数组，也就是滚动数组，为什么叫滚动数组看完接下来的分析你就懂了！
那么我们通过01背包，来彻底讲一讲滚动数组！
接下来还是用如下这个例子来进行讲解：
weight = [1, 3, 4]
value = [15, 20, 30]
一维dp数组（滚动数组）
对于背包问题其实状态都是可以压缩的!
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[
2024-12-05
1.6k 字
6 分钟
动态规划-01背包理论基础(一)
动态规划：01背包理论基础(一)
背包分类图
什么是01背包？
01背包
有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
关于其他背包
除01背包以外其他类型的背包，面试几乎不会问，都是竞赛级别的了，leetcode上连多重背包的题目都没有，所以题库也告诉我们，01背包和完全背包就够用了。
而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。
所以背包问题的理论基础重中之重是01背包，一定要理解透！
举个栗子
weight = [1
2024-12-02
1.5k 字
6 分钟
LeetCode-不同路径
题目-不同路径I
一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为Start）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为Finish）。
问总共有多少条不同的路径？
示例1
输入：m = 3, n = 7
输出：28
示例2
输入：m = 2, n = 3
输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例3
输入：m = 7, n = 3
输出：28
示例4
输入：m
