动态规划--一维dp和二维dp

在解决背包问题时，使用一维动态规划数组和二维动态规划数组都是常见的方法，选择哪种方式取决于问题的特点和解法的需要。

使用一维DP数组的情况：

1. 状态转移方程只涉及到上一行的元素：

   • 当状态转移方程只涉及到上一行的元素时，可以使用一维DP数组。这样能够降低空间复杂度，使算法更为简洁。

2. 问题中只需要考虑当前状态的前一个状态：

   • 如果问题中只需要考虑当前状态和前一个状态之间的关系，而不需要考虑更远的状态，可以选择使用一维DP数组。

使用二维DP数组的情况：

1. 状态转移方程涉及到上一行和当前行的元素：

   • 当状态转移方程涉及到上一行和当前行的元素时，通常需要使用二维DP数组。例如，背包问题中的状态转移方程常常涉及到两个维度，一个表示物品，一个表示背包容量。

2. 问题需要保留更多的信息：

   • 如果问题需要保留更多的信息，可能需要使用二维DP数组来存储这些额外的信息，以便后续计算。例如，记录达到当前状态的路径、组合方式等。

3. 更直观的表示状态：

   • 对于一些复杂的问题，使用二维DP数组可以更直观地表示问题的状态和状态之间的关系，提高代码的可读性。

示例：

一维DP数组示例：

dp = [0] * (target+1)
for num in nums:
    for i in range(target, num-1, -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][j] = dp[i-1][j]
        if j >= nums[i-1]:
            dp[i][j] += dp[i-1][j-nums[i-1]]

总的来说，选择使用一维DP数组还是二维DP数组，取决于问题的特点和解法的需要。在一些情况下，通过巧妙的设计，可以将二维DP数组优化成一维DP数组。

上一行和当前行的含义
在动态规划中，经常会用到“上一行”和“当前行”这两个概念，尤其是在使用二维动态规划数组时。这两者的区别在于它们对应于不同的状态或阶段。

1. 上一行（Previous Row）：

   • 指的是当前阶段之前的一个阶段，也就是在DP数组中的上一行。
   • 在二维DP数组中，通常表示为dp[i-1][...]，其中i是当前行的索引。
   • 上一行对应于之前的状态，用来计算当前行的状态。

2. 当前行（Current Row）：

   • 指的是当前阶段，也就是在DP数组中的当前行。
   • 在二维DP数组中，通常表示为dp[i][...]，其中i是当前行的索引。
   • 当前行对应于当前状态，是根据上一行的状态计算得到的。

在讨论背包问题时，这两者的具体含义可以理解为：

• 上一行： 表示考虑到当前物品之前的状态，即在选择当前物品之前的状态。
• 当前行： 表示在考虑当前物品时的状态，即在选择当前物品后的状态。

具体到代码中，通过这两者的概念，我们可以方便地设计状态转移方程，使用前一行的信息来更新当前行的信息，从而实现动态规划的递推过程。