本博客筆記內容來源于靈神，視頻鏈接如下：https://www.bilibili.com/video/BV16Y411v7Y6?vd_source=7414087e971fef9431117e44d8ba61a7&spm_id_from=333.788.player.switch

01背包

計算了f[i+1]，f[i]就沒用了，相當于每時每刻只有兩個數組在參與運算：


494題是求方案數的，要初始化成 0。
如果是恰好型背包并且要計算最大最小，那么初始值就和 inf 有關。

力扣494題：

對于至少/至多的變形問題，變形類似：

完全背包

力扣322題：

其中：從二維遞推式來理解，
例如01背包，更新f【c】的值需要的是當前f【c】和上一個狀態的f【c-w】，因為我們現在之后一個數組，若是正序，f【c-w】就更新過了，也就不是上一個狀態的值了，所以必須逆序；
若是完全背包，更新f【c】的值需要的是當前f【c】和當前狀態的f【c-w】，需要的就是更新過的值，所以正序是沒問題的。

例題：力扣2915. 和為目標值的最長子序列的長度

class Solution:def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:# 先使用遞歸# 恰好等于target ==背包容量# 長度即選物品，其價值為1# 只能選一次：01背包問題n = len(nums)# 1.遞歸：@cachedef dfs(i,c):if i<0:return 0 if c==0 else -infif c< nums[i]:return dfs(i-1,c)return max(dfs(i-1,c),dfs(i-1,c-nums[i])+1)ans= dfs(n-1,target)dfs.cache_clear()return ans if ans>-1 else -1# 2. 轉為遞推:dp[i+1][c]= max(dp[i][c],dp[i][c-nums[i]]+1) 整體加了1dp =[[-inf]*(target+1) for _ in range(n+1)]dp[0][0]=0for i,x in enumerate(nums):for c in range(target+1):if c<x:dp[i+1][c]=dp[i][c]else:dp[i+1][c]= max(dp[i][c],dp[i][c-x]+1)ans = dp[n][target]return ans if ans>-1 else -1# 3. 進一步優化為滾動數組dp =[[-inf]*(target+1) for _ in range(2)]dp[0][0]=0for i,x in enumerate(nums):for c in range(target+1):if c<x:dp[(i+1)%2][c]=dp[i%2][c]else:dp[(i+1)%2][c]= max(dp[i%2][c],dp[i%2][c-x]+1)ans = dp[n%2][target]  # 記得這里也要%2return ans if ans>-1 else -1#  4. 進一步優化為1維滾動數組dp =[-inf]*(target+1)dp[0]=0for x in nums:for c in range(target,x-1,-1):if c<x:dp[c] = dp[c]else:dp[c]= max(dp[c],dp[c-x]+1)ans = dp[target]  return ans if ans>-1 else -1