动态规划--一维dp和二维dp
在解决背包问题时，使用一维动态规划数组和二维动态规划数组都是常见的方法，选择哪种方式取决于问题的特点和解法的需要。
使用一维DP数组的情况：
-
状态转移方程只涉及到上一行的元素：
- 当状态转移方程只涉及到上一行的元素时，可以使用一维DP数组。这样能够降低空间复杂度，使算法更为简洁。
-
问题中只需要考虑当前状态的前一个状态：
- 如果问题中只需要考虑当前状态和前一个状态之间的关系，而不需要考虑更远的状态，可以选择使用一维DP数组。
使用二维DP数组的情况：
-
状态转移方程涉及到上一行和当前行的元素：
- 当状态转移方程涉及到上一行和当前行的元素时，通常需要使用二维DP数组。例如，背包问题中的状态转移方程常常涉及到两个维度，一个表示物品，一个表示背包容量。
-
问题需要保留更多的信息：
- 如果问题需要保留更多的信息，可能需要使用二维DP数组来存储这些额外的信息，以便后续计算。例如，记录达到当前状态的路径、组合方式等。
-
更直观的表示状态：
- 对于一些复杂的问题，使用二维DP数组可以更直观地表示问题的状态和状态之间的关系，提高代码的可读性。
示例：
一维DP数组示例：
dp = [0] * (target+1)
for num in nums:
for i in range(target, num-1, -1): #0-1背包一维常倒序（倒序为了避免重复），完全背包常正序
dp[i] += dp[i-num]
二维DP数组示例：
dp = [[0] * (target+1) for _ in range(len(nums)+1)]
for i in range(1, len(nums)+1):
for j in range(target+1): #二维常正序 不同行（dp[i][..]和dp[i-1][..]）不会重复
dp[i][j] = dp[i-1][j]
if j >= nums[i-1]:
dp[i][j] += dp[i-1][j-nums[i-1]]
总的来说，选择使用一维DP数组还是二维DP数组，取决于问题的特点和解法的需要。在一些情况下，通过巧妙的设计，可以将二维DP数组优化成一维DP数组。
上一行和当前行的含义
在动态规划中，经常会用到“上一行”和“当前行”这两个概念，尤其是在使用二维动态规划数组时。这两者的区别在于它们对应于不同的状态或阶段。
-
上一行（Previous Row）：
- 指的是当前阶段之前的一个阶段，也就是在DP数组中的上一行。
- 在二维DP数组中，通常表示为
dp[i-1][...]，其中i是当前行的索引。 - 上一行对应于之前的状态，用来计算当前行的状态。
-
当前行（Current Row）：
- 指的是当前阶段，也就是在DP数组中的当前行。
- 在二维DP数组中，通常表示为
dp[i][...]，其中i是当前行的索引。 - 当前行对应于当前状态，是根据上一行的状态计算得到的。
在讨论背包问题时，这两者的具体含义可以理解为：
- 上一行： 表示考虑到当前物品之前的状态，即在选择当前物品之前的状态。
- 当前行： 表示在考虑当前物品时的状态，即在选择当前物品后的状态。
具体到代码中，通过这两者的概念，我们可以方便地设计状态转移方程，使用前一行的信息来更新当前行的信息，从而实现动态规划的递推过程。