ArMiku Blog

# 买卖股票的最佳时机 II 题目链接🔗 确定 dp 数组以及下标的含义 dp [i][0]: 表示第 i 天持有股票所得现金。 dp [i][1]: 表示第 i 天不持有股票所得最多现金。 确定递推公式 第 i 天持有股票即 dp [i][0]， 可以由两个状态推出来： 第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp [i - 1][0] 第 i 天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp [i - 1][1] - prices [i] 第 i 天不持有股票即 dp [i][1] 的情况，...

# 打家劫舍 题目链接🔗 当前房屋偷不偷取决于前一个和前两个房间是否偷了。 当前状态和之前状态有依赖关系，使用动态规划。 确定 dp 数组以及下标的含义 dp [i]: 考虑包括下标 i 以内的房屋，最多可以偷的金额为 dp [i]。 确定递推公式 决定 dp [i] 的因素就是第 i 房间偷还是不偷。 如果偷第 i 房间，那么 dp [i] = dp [i - 2] + nums [i] ，即：第 i-1 房一定是不考虑的，找出 下标 i-2（包括 i-2）以内的房屋，最多可以偷窃的金额为 dp [i-2] 加上第 i 房间偷到的钱。 如果不偷第 i 房间，那么 dp [i] =...

单词拆分题目链接🔗 单词是物品，字符串s是背包，单词能否组成字符串s就是问物品能不能装满背包。 拆分时可以重复使用字典中的单词，就是完全背包。 确定dp数组和下标含义 dp[i]: 字符串长度为i，dp[i]为true，表示可以拆分成一个或者多个在字典中出现的单词。 确定递推公式 如果确定dp[j] == true，且[j, i]这个区间的子串出现在字典里，那么dp[i] = true。 递推公式就是，如果[j, i] 这个区间的子串出现在字典里 && dp[j]是true，那么 dp[i] =...

# 组合总和 IV 题目链接🔗 题目提到顺序不同的序列被视作不同的组合。，所以不是在求组合而是在求排列。 确定 dp 数组以及下标的含义 dp [i]: 凑成目标正整数为 i 的排列个数为 dp [i]。 确定递推公式 dp [i] 可以由 dp [i-nums [j]] 推导出来，因此递推公式为：$$dp [i] += dp [i-nums [j]]$$ dp 数组如何初始化 因为递推公式的原因，dp [0] = 1 才能让其他 dp [i] 有数值基础，其他下标初始化为 0。 确定遍历顺序 要求的是排列数，因此外层遍历背包，内层遍历物品，内层从前向后遍历。 举例推导...

# 目标和 题目链接🔗 结果 target 可以将数组分为两部分，左组合 left - 右组合 right = target。 left + right = sum，而数组总和是固定的，因此 right = sum - left。 那么 left - (sum - left) = target，left = (target + sum) / 2。 target 和 sum 是固定值，那么问题就转化为在数组中求 left 的组合。 转化为背包问题就是，装满容量为 left 的背包，有几种方法。每个数只能取一次，就是 01 背包。 确认 dp 数组及下标含义 dp [j]: 填满容积为 j...

# 01 背包理论基础 01 背包模板题：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight [i]，得到的价值是 value [i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 背包最大重量为 4，物品为： 重量 价值 物品 0 1 15 物品 1 3 20 物品 2 4 30 # 二维 dp 数组 确定 dp 数组以及下标含义 dp [i][j]: 从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。 确定递推公式 两个方向可推导出 dp [i][j]： 不放物品 i: 由 dp [i...

# 不同路径 题目链接🔗 机器人要从 (0, 0) 走到 (m-1, n-1)。 确定 dp 数组以及下标的含义 dp [i][j]: 从 (0, 0) 到 (i, j) 有 dp [i][j] 条不同的路径。 确定递推公式 dp 可以从两个方向推导出来，即 dp [i-1][j] 和 dp [i][j-1]。 那么dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1] dp 数组初始化 dp [i][0] 和 dp [0][j] 都为 0，因为从...

# 动态规划理论基础 动态规划中每一个状态一定是由上一个状态推导出来的。 对于动态规划问题，大致分为五步： 确定 dp 数组以及下标的含义 确定递推公式 dp 数组如何初始化 确定遍历顺序 举例推导 dp 数组 # 爬楼梯 题目链接🔗 确定 dp 数组以及下标的含义 dp [i]: 爬到第 i 层有 dp [i] 种方法。 确定递推公式 当前楼层可以由上一楼层或上上一楼层到达，因此 dp [i] 可以由两个方向推导出来。 首先是 dp [i-1]，上 i-1 层，有 dp [i-1] 种方法，那么再走一次爬一个楼层就是 dp [i]。 其次是 dp [i-2]，上 i-2 层，有...

# 单调递增的数字 题目链接🔗 一旦出现 strNum[i - 1] > strNum[i] 的情况（非单调递增），首先想让 strNum [i - 1]--，然后 strNum [i] 给为 9。 从后向前遍历，重复利用上次比较的结果，此时局部最优可以推出全局最优。 class Solution {public: int monotoneIncreasingDigits(int N) { string strNum = to_string(N); //flag 用来标记赋值 9 从哪里开始 // 设置为这个默认值，为了防止第二个 for...

# 用最少的箭引爆气球 题目链接🔗 局部最优：当气球出现重叠，一起射，所用弓箭最少。 全局最优：把所有气球射爆所用弓箭最少。 为了让气球尽可能的重叠，需要对数组进行排序。 按照起始位置排序，从前向后遍历气球数组，靠左尽可能让气球重复。 如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。 class Solution {private: static bool cmp(const vector<int>& a, const vector<int>& b) {...