DAY16 2026.03.28
LeetCode322 零钱兑换 [动态规划]
完全背包问题。dp[j]表示容量为j的背包装满最少需要dp[j]个物品，不放物品i：dp[j] = dp[j]，放物品i：dp[j] = dp[j-nums[i]] + 1。状态转移方程为dp[j] = Math.min(dp[j]，dp[j-nums[i]] + 1)
初始化，dp[0] = 0，考虑到递推公式取最小值，其他非零下标应初始化为最大值
遍历顺序，外层for顺序遍历物品，内层for循环遍历背包，求的是组合数
特别的，内层遍历背包时，当遇到dp[j-nums[i]]为初始值时，说明它目前还没有办法塞满，此时也无法由它将当前的背包塞满，不进入状态转移方程，继续往下遍历
LeetCode139 单词拆分 [动态规划]
完全背包问题。单词就是物品，字符串s就是背包，单词能否组成字符串s，就是物品能否把背包装满；拆分时可以重复使用单词，就是可以重复使用物品，属于完全背包问题
字符串的长度为i，若字符串s[0，i]的字符串能被单词组成，则dp[i] = true
递推公式：如果s[i，j]可以被单词组成，且dp[i] = true，那么dp[j] = true
初始化：dp[0] = true，作为递推公式的基础，无实际意义，其他非零下标初始化为false
外层for顺序遍历背包，内层for顺序遍历物品，求的是排列数
LeetCode300 最长递增子序列 [动态规划]
dp[i]表示i之前包括i的以nums[i]为结尾的最长严格递增子序列的长度。i在后，j在0到i之间，如果nums[i]大于nums[j]，dp[i] = Math.max(dp[i], dp[j]+1)
dp数组所有下标初始化为1，因为每个元素其本身也算作一个严格递增子序列
LeetCode152 乘积最大子数组 [动态规划]
在遍历nums的同时，维护两个数组：右端点下标为i的子数组的最大乘积fmax[i]，右端点下标为i的子数组的最小乘积fmin[i]
- 当nums[i]单独组成一个子数组，fmax[i] = nums[i]
- nums[i]和前面的子数组拼起来，那么fmax[i] = fmax[i-1]*nums[i]
- fmin[i]同理
把fmax和fmin都算一下，这样就不用判断nums[i]是正是负了，三种情况取最大值：
-
fmax[i] = max(nums[i], fmax[i-1]*nums[i], fmin[i-1]*nums[i])
-
fmin[i] = min(nums[i], fmax[i-1]*nums[i], fmin[i-1]*nums[i])
初始化，fmax[0] = fmin[0] = nums[0]，result也初始化为nums[0]
LeetCode416 分割等和子集 [动态规划]
可以抽象为01背包问题，第i个物品的重量和价值都等于nums[i]。dp[j]表示容量为j的背包所能装的最大价值
状态转移方程 dp[j] = Math.max(dp[j]，dp[j-weight[i]] + value[i])
- 不放第i个物品时，dp[j] = dp[j]
- 放第i个物品时，dp[j] = dp[j-weight[i]] + value[i]
dp数组全部初始化为0
根据递推公式 dp[j] = Math.max(dp[j]，dp[j-weight[i]] + value[i])，i为物品，j为背包，双重for循环外层顺序遍历物品i，内层倒序遍历背包j