给定总和的最短子序列长度 Memoized 解决方案给出错误答案

Question

为给定总和找到最短子序列长度的 Bruteforce 方法是为 main 方法中给定的输入提供正确的 2、2、9 输出，但在记忆时得到错误的输出 3、3、9。有人可以帮忙吗？谢谢

class ShortestSubsequenceWithSum {    
  public static int shortestSubsequenceWithSum(int[] num, int s, int cnt, Integer []dp) {
    if(s == 0){
      return cnt;
    }
    if(s < 0){
      return Integer.MAX_VALUE;
    }
    if(dp[s] != null){
      return dp[s];
    }
    int res = Integer.MAX_VALUE;
    for(int i=0; i<num.length; i++){
      int rem = s - num[i];
      int ways = shortestSubsequenceWithSum(num, rem, cnt +1, dp);
      res = Math.min(res, ways);
      dp[s] = res;
    }
    // System.out.println("Returning value at @ " + s);
    return dp[s];
  }
  
  public static void main(String[] args) {
    int[] num = {1, 1, 2, 3};
    Integer dp[] = new Integer[5+1];
    System.out.println(shortestSubsequenceWithSum(num, 5,0, dp));
    num = new int[]{1, 2, 7, 1};
    dp = new Integer[9+1];
    System.out.println(shortestSubsequenceWithSum(num, 9,0, dp));
    num = new int[]{1};
    dp = new Integer[9+1];
    System.out.println(shortestSubsequenceWithSum(num, 9,0, dp));
  }
}

Answer 1

这里的问题是您的递归方法目前的工作方式不适合记忆。

您似乎在使用 dp 数组来存储当前已知的求和所需的最少数字。所以 dp[5] 将是使总数为 5 所需的最少数字数。如果 dp[5] = 3 那么你已经找到了一种方法，可以使三个数字的总数为 5，但还没有找到方法从少于三个数字中得到 5。

您的方法 shortestSubsequenceWithSum 目前 return 是达到总数所需的最小数字计数加上当前进行的递归调用的数量。如果您想使用记忆，则必须将此方法调整为 return 达到总数所需的最小数字计数，而不管到目前为止有多少级递归。

您需要进行的更改是：

在 s == 0 案例的处理中，return 0 而不是 cnt。这表示能够从零个数字中得出总和为 0。
将行 dp[s] = res 更改为 dp[s] = res + 1。 res 包含到目前为止 i 的每个值组成 s - num[i] 的数字的（最小）计数，因此我们在加起来的组合中选择 num[i] 加 1至 s.

这些应该足以让您的代码正常工作。但是，实际上您可以立即将行 dp[s] = res + 1 移到 for 循环之外：我们不妨等待 res 的最终值，然后再将其分配给 dp[s]。您还可以从方法 shortestSubsequenceWithSum 中删除参数 cnt，以及对该方法的所有调用，因为不再使用此参数。

这应该会给您留下以下内容：

    /**
     * Returns the minimum count of numbers from the given array that can
     * make up a total. The same number can be chosen multiple times.
     * @param num The numbers that can be chosen from.
     * @param s The total to reach.
     * @param dp An array that memoizes pre-computed values of this method.
     * @return The minimum count of numbers from 'num' that totals 's'.
     */
    public static int shortestSubsequenceWithSum(int[] num, int s, Integer []dp) {
        if(s == 0){
            return 0;
        }
        if(s < 0){
            return Integer.MAX_VALUE;
        }
        if(dp[s] != null){
            return dp[s];
        }
        int res = Integer.MAX_VALUE;
        for(int i=0; i<num.length; i++){
            int rem = s - num[i];
            int ways = shortestSubsequenceWithSum(num, rem, dp);
            res = Math.min(res, ways);
        }
        dp[s] = res + 1;
        // System.out.println("Returning value at @ " + s);
        return dp[s];
    }

最后，我会注意到这段代码不处理没有组合加起来等于总数的情况。我将修复它作为你的练习，请参见下面的示例测试用例：

int[] num = {2, 4, 6};
Integer dp[] = new Integer[5+1];
System.out.println(shortestSubsequenceWithSum(num, 5, dp));

给定总和的最短子序列长度 Memoized 解决方案给出错误答案

Shortest subsequence length for a given sum Memoized solution giving wrong answer

java

algorithm

recursion

dynamic-programming

memoization