开始完全背包
不同于01背包，完全背包的特色在于元素可以重复拿取， 因此在递归公式和遍历顺序上都有些许不同。
leetcode 518 零钱兑换 ||
在组合方式中所用到的递推公式是dp[ j ] = dp[ j - coins[i]] + dp[ j ]
对于coins[ i ] > j 的情况，for j in range(coin[ i ], amount + 1)不会执行，即实现dp[ i ][j] = dp[ i - 1][j]
class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1for i in range(len(coins)):for j in range(coins[i], amount + 1):dp[j] += dp[j - coins[i]]return dp[amount]leetcode 377 组合总和 IV
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
测试代码：
from typing import Listclass Solution:# 方式1: 先遍历物品，再遍历背包（求组合数）def change_order1(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1paths = [[] for _ in range(amount + 1)] # 记录路径paths[0].append([]) # 初始化空组合for coin in coins: # 遍历物品for j in range(coin, amount + 1): # 遍历背包dp[j] += dp[j - coin]for path in paths[j - coin]: # 复制路径paths[j].append(path + [coin])# 打印所有组合print(f"先遍历物品，再遍历背包（组合数: {dp[amount]}）：")for path in paths[amount]:print(path)return dp[amount]# 方式2: 先遍历背包，再遍历物品（求排列数）def change_order2(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1paths = [[] for _ in range(amount + 1)] # 记录路径paths[0].append([]) # 初始化空排列for j in range(amount + 1): # 遍历背包for coin in coins: # 遍历物品if j - coin >= 0:dp[j] += dp[j - coin]for path in paths[j - coin]: # 复制路径paths[j].append(path + [coin])# 打印所有排列print(f"先遍历背包，再遍历物品（排列数: {dp[amount]}）：")for path in paths[amount]:print(path)return dp[amount]# PyCharm 运行示例
if __name__ == "__main__":solution = Solution()amount = 5coins = [1, 2, 5]# 调用两种方法result1 = solution.change_order1(amount, coins)result2 = solution.change_order2(amount, coins)print(f"先遍历物品，再遍历背包（总组合数）：{result1}")print(f"先遍历背包，再遍历物品（总排列数）：{result2}")
解题思路：
class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * (target + 1)dp[0] = 1for i in range(1, target + 1):for j in range(len(nums)):if i - nums[j] >= 0:dp[i] += dp[i - nums[j]]return dp[target]卡码网 57 爬楼梯
分析好重量m和包容量n可解
import sysdef climbing_stairs(n, m):dp = [0] * (n + 1)dp[0] = 1for j in range(1, n + 1):for i in range(1, m + 1):if j >= i:dp[j] += dp[j - i]return dp[n]if __name__ == '__main__':n, m = list(map(int, input().split()))print(climbing_stairs(n, m))
)
