代码随想录day40 动态规划（5）

52. 携带研究材料（第七期模拟笔试） (kamacoder.com) 

完全背包，可重复放入物品，需要用一维滚动数组从前往后遍历。

由于第0个物品和后面物品的转移方程没有区别，可以不额外初始化dp数组，直接用元素全0的dp从第0个物品开始遍历。

class solution:def maxval(self, capacity, luggages):dp = [0 for _ in range(capacity + 1)]for i in range(len(luggages)):w = luggages[i][0]v = luggages[i][1]for j in range(w, capacity+1):dp[j] = max(dp[j], v + dp[j-w])return dp[-1]if __name__ == "__main__":N, capacity = map(int, input().split())luggages = []for i in range(N):cur = list(map(int, input().split()))luggages.append(cur)res = solution().maxval(capacity, luggages)print(res)

518. 零钱兑换 II - 力扣（LeetCode） 

dp初始化：为了避免dp元素始终为0，令dp[0]=1，其余=0。* amount > 0时，空集不算一种组合，所以不能将dp所有元素初始化为1。当coins[i]不大于当前上限j，进入第二层循环，想象coins[0]==j的情况，dp[j] = 0+1 = 1，这个组合数是合理的。

由于物品可重复，从前向后遍历滚动数组。求组合数，累加。

class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0 for _ in range(amount+1)] #dp[j]:不超过j金额且尽和可能大的组合数dp[0] = 1for i in range(len(coins)):for j in range(coins[i], amount+1):dp[j] += dp[j-coins[i]]return dp[-1]

先遍历物品再遍历背包上限=>组合数

 先遍历背包上限再遍历物品=>排列数

377. 组合总和 Ⅳ - 力扣（LeetCode）

求排列数，需要先遍历target再遍历物品。

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0 for _ in range(target+1)]dp[0] = 1for j in range(target+1):for num in nums:if j >= num:dp[j] += dp[j-num]return dp[-1] 

 

57. 爬楼梯（第八期模拟笔试） (kamacoder.com) 

class sol:def ways(self, n, m):dp = [0 for _ in range(n+1)]dp[0] = 1 for j in range(n+1):for i in range(1, m+1):if j >= i:dp[j] += dp[j-i]return dp[-1]if __name__ == "__main__":n, m = map(int, input().split())res = sol().ways(n, m)print(res)