找到給定總和的最短子序列長度的 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));
}
}
uj5u.com熱心網友回復：
這里的問題是您的遞回方法目前的作業方式不適合記憶。
看起來您正在使用您的dp陣列來存盤當前已知的總計所需的最小數量。因此dp[5]，使總數為 5 所需的最小數字計數也是如此。如果dp[5] = 3您已經找到了一種從三個數字中合成 5 的方法，但還沒有找到一種從少于三個數字中合成 5 的方法。
您的方法shortestSubsequenceWithSum目前回傳達到總數所需的最小數量加上當前進行的遞回呼叫的數量。如果你想使用記憶，你將不得不調整這個方法來回傳達到總數所需的最小數字計數，不管到目前為止有多少級遞回。
您需要進行的更改是：
- 在辦理案件
s == 0時，退而0不退cnt。這表示能夠從零數字中得到總計 0。 - 將行更改
dp[s] = res為dp[s] = res 1。res包含構成到目前為止s - num[i]每個值的（最小）數字計數，因此我們加 1 用于選擇組合，加起來為.inum[i]s
這些應該足以讓您的代碼正常作業。但是，您實際上可以將行dp[s] = res 1立即移出for回圈：我們不妨等待 的最終值，res然后再將其分配給dp[s]. 您還可以cnt從您的方法中洗掉引數shortestSubsequenceWithSum，以及對該方法的所有呼叫，因為該引數不再被使用。
這應該會給您以下內容：
/**
* 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));
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/411299.html
標籤：