https://www.programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85
对于一维dp
注：纯完全背包问题，其for循环的先后循环是可以颠倒的！
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
注：dp[j]：凑成总金额j的货币组合数为dp[j], dp[0] = 1
首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。
从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
tips：求的方法所以是组合数，完全背包，硬币数相当于物品，且可以用多次。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。
从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
# 组合0的金额 也有0这1种方法
dp[0] = 1
# 完全背包（背包容量正序），组合数 （先物品后背包）,求方法（之前的方法数累加求和，不加1）
for coin in coins:
for j in range(coin, amount + 1, 1):
dp[j] += dp[j - coin]
return dp[-1]
tips:排序数，先背包，后物品,dp[i]: 凑成目标正整数为i的排列个数为dp[i]
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
# 完全背包（背包容量正序），排序数 （先背包后物品）,求方法数（之前的方法数累加求和，不加1）
for j in range(target + 1):
for num in nums:
if j >= num:
dp[j] += dp[j - num]
return dp[-1]
tips ：377. 组合总和 Ⅳ (opens new window)基本就是一道题了。
在动态规划：494.目标和 (opens new window)、 动态规划：518.零钱兑换II (opens new window)、动态规划：377. 组合总和 Ⅳ (opens new window)中我们都讲过了，求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0]*(n + 1)
dp[0] = 1
m = 2
# 遍历背包
for j in range(n + 1):
# 遍历物品 可以从选[1,m]阶楼梯
for step in range(1, m + 1):
if j >= step:
dp[j] += dp[j - step]
return dp[n]
tips：这里求的是最少硬币的个数，所以如果选了coin[i] 则还剩下j - coin[i]的空间 ，同时硬币个数加1，所以递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
初始化：
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
其他下标对应的数值呢？
考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
maxv = float('inf')
dp = [maxv] * (amount + 1)
dp[0] = 0
# 一个物品用多次，完全背包（背包容量正序），排序数、组合数不影响所以顺序不影响（这里先物品后背包）,求最小数（min，加1）
for coin in coins:
for j in range(coin, amount + 1, 1):
dp[j] = min(dp[j], dp[j - coin] + 1)
# 判断存在不存在这样的组成
if dp[-1] != maxv:
return dp[-1]
else:
return -1
tips：完全背包（背包容量正序），最小值（min，+ 1），内外顺序都可以
class Solution:
def numSquares(self, n: int) -> int:
maxv = float('inf')
dp = [maxv] * (n + 1)
dp[0] = 0
#完全背包（背包容量正序），顺序不影响（这里先物品后背包）,求最小数（min，加1）
# i取值 [1,n的开平方+1]
for i in range(1, int(n**0.5) + 1):
for j in range(i*i, n + 1, 1):
dp[j] = min(dp[j], dp[j - i * i] + 1)
return dp[-1]
总结：
但是！！ 组合数先物品后背包，排序数先背包后物品。