java - 具有组合和内循环和外循环可互换的动态编程？

Question

我对组合和的动态规划解决方案有点困惑，给你一个数字列表和一个目标总和，你想计算你可以通过多少种方式求和到这个目标总和。数字可以重复使用多次。我对内循环和外循环是否可以互换感到困惑。有人可以解释以下两者之间的区别，在什么情况下我们会使用一个而不使用另一个，或者它们是相同的。

int [] counts = new int[total];
counts[0] = 1;

// (1) 
for(int i = 0; i <= total; i++) {
   for(int j = 0; j < nums.length; j++) {
       if(i >= nums[j])
          counts[i] += counts[i - nums[j]];
   }
}

// (2)
for(int j = 0; j < nums.length; j++)
   for(int i = nums[j]; i <= total; i++) {
       counts[i] += counts[i - nums[j]];
   }
}

Answer 1

这两个版本确实不同，产生不同的结果。

我将在下面的所有示例中使用 nums = {2, 3}。

版本 1 从 nums 中查找元素的排序 组合数，其总和为 total。它通过遍历所有“小计”并计算有多少组合具有正确的总和来实现这一点，但它不会跟踪元素。例如，5 的计数将为 2。这是使用第一个元素(值为 2)并在 nums[3] 中找到 1 个组合以及第二个元素的另一个组合(值为3) 与 nums[2] 中的 1 组合。您应该注意，这两种组合都使用单个 2 和单个 3，但它们代表 2 个不同的有序列表 [2, 3] & [3, 2]。

另一方面，版本 2 从 nums 中查找元素的无序 组合数，其总和为 total。它通过计算有多少组合具有正确的总和(每个小计)来做到这一点，但与版本 1 相反，它在移动到下一个元素之前完全“使用”每个元素，从而避免同一组的不同排序。当使用第一个元素 (2) 计算小计时，所有计数最初都将为 0(除了 0 总和标记)，任何偶数小计都将获得新计数 1。当使用下一个元素时，就好像它在后面所有 2 都已经在组中，因此，与版本 1 相反，只有 [2, 3] 被计算在内，而不是 [3, 2]。

顺便说一下，nums 中元素的顺序不会影响结果，正如解释的逻辑所理解的那样。