动态规划的主要解题步骤分为三步：
- a.定义子问题（将固定值改成随意值）
-
b. 定义状态数组（数组中的每一个位置代表的意义，数组中的值代表的意义） -
c. 定义状态转移方程（确定当前值与前面值的关系）
个人感觉能不能想到用动态规划解题，真的是随缘 哈哈哈哈
这篇文章主要看三个问题：
-
排列数 ——假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解：这个题一看，动态规划很简单。边界问题：
dp[0] = 1
dp[1] = 1
状态转移方程：
dp[i] = dp[i-1] + dp[i-2]
结果：
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]
简单优化
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
# 不只有1 2 还有其他值，给的是一个list时
for j in range(1,3):
dp[i] += dp[i - j]
return dp[-1]
- 组合数
同理，使用动态规划：
边界问题：
dp[0] = 1
状态转移方程：
dp[i] = dp[i] + dp[i-x]
结果：
def change(self, amount: int, coins: list[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for x in coins:
for j in range(x, amount + 1):
dp[j] = dp[j] + dp[j - x]
return dp[-1]
- 等于x的个数
在数组nums 中选取若干元素，使得这些元素之和等于neg，计算选取元素的方案数。
例：nums = [1,2,3,4,5] neg = 10 则选择方案一共有3种（1，2，3，4；1，4，5；2，3，5）
使用动态规划求解：
边界问题：
dp[0] = 1
状态转移方程：
dp[i] = dp[i] + dp[i-x]
结果：
def change(self, amount: int, coins: list[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for x in coins:
for j in range(x, amount + 1):
dp[j] = dp[j] + dp[j - x]
return dp[-1]
不难发现，上面三份代码，只存在微小的差别，第一份和第二份相比，双重循环的关系相反，导致结果一个是排列，一个是组合；第二份和第三份相比，内循环一个是正序，一个是倒序，导致的结果是每个数可使用n次和每个数最多可使用一次的区别。
所以
要求是排列时：正序，nums位于内循环
要求是组合时：正序，nums位于外循环
要求是数字最多可使用一次时：倒序，nums位于外循环