2017-06-02 56 views
1

我已經得到了非記憶代碼正常工作,它計算了'n'可以表示的方式的數量,給出了m個可能的值。但是我不能在下面的代碼中找出爲什麼memoization表memoNM返回0而不是在這種情況下是24的答案。表memoNM只是在遞歸樹中存儲以前計算的值以便更快地查找。有人可以幫幫我嗎?記憶表不能正常工作

import java.util.ArrayList; 
    import java.util.Arrays; 

    public class coinChange { 
    //Find all ways of representing n in given m inputs 
    public static void main(String args[]) { 
     ArrayList<Integer> coinTypes = new ArrayList<Integer>(Arrays.asList(25, 
       10, 5, 1));//m 
     int n = 100; 
     int[][] memoNM = new int[n + 1][coinTypes.size() + 1]; 
     // Initialize memoNM 

     for (int i = 0; i < memoNM.length; i++) { 
      for (int j = 0; j < memoNM[0].length; j++) { 
       memoNM[i][j] = 0; 
      } 
     } 

     int ans = coinChange.coinChange1(n, coinTypes, 0, memoNM); 
     System.out.println(ans); 
    } 

    public static int coinChange1(int n, ArrayList<Integer> coinTypes, 
      int indexFrom, int[][] memoNM) { 
     // System.out.println("Coin Types: " + coinTypes.toString() + ", n is: " 
     // + n + ", m is : " + coinTypes.size()); 
     if (n < 0) { 
      return 0; 
     } 
     if (indexFrom >= coinTypes.size()) { 
      return 0; 
     } 
     if (memoNM[n][indexFrom] > 0) { 
      return memoNM[n][indexFrom]; 
     } 

     if (n == 0) { 
      return 1; 
     } 

     /*System.out.println("n is: " + n + " m is: " 
       + (coinTypes.size() - indexFrom) + ", memo[n][m] is: " 
       + memoNM[n][indexFrom]); 
*/ 
     memoNM[n][indexFrom] += coinChange1(n - coinTypes.get(indexFrom), 
       coinTypes, indexFrom, memoNM); 
     ++indexFrom; 
     memoNM[n][indexFrom] += coinChange1(n, coinTypes, indexFrom, memoNM); 
     return memoNM[n][indexFrom]; 
    } 
} 

更新: 我實現了相同的代碼使用上面一個HashMap,作爲查找,而不是一個表,但我的答案是錯的。 n的正確答案= 6,M = 4應該是9

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 

public class coinChangeMap { 
    // For an excellent explanation see section 1.7.5 in 
    // http://composingprograms.com/pages/17-recursive-functions.html 
    public static void main(String args[]) { 
     ArrayList<Integer> coinTypes = new ArrayList<Integer>(Arrays.asList(4, 
       3, 2, 1)); 
     int n = 6; 
     HashMap<Tuple, Integer> memoMap = new HashMap<Tuple, Integer>(); 

     int ans = coinChangeMap1(n, coinTypes, 0, memoMap); 
    memoMap.toString(); 
    System.out.println(ans); 

} 

public static int coinChangeMap1(int n, ArrayList<Integer> coinTypes, 
     int indexFrom, HashMap<Tuple, Integer> memoMap) { 
    // System.out.println("Coin Types: " + coinTypes.toString() + ", n is: " 
    // + n + ", m is : " + coinTypes.size()); 
    if (n < 0) { 
     return 0; 
    } 
    if (indexFrom >= coinTypes.size()) { 
     return 0; 
    } 

    if (n == 0) { 
     return 1; 
    } 
    Tuple tup = new Tuple(n, indexFrom); 
    if (memoMap.containsKey(tup)) { 
     return memoMap.get(tup); 
    } 
    /* 
    * System.out.println("n is: " + n + " m is: " + (coinTypes.size() - 
    * indexFrom) + ", memo[n][m] is: " + memoNM[n][indexFrom]); 
    */ 
    int leftAns = coinChangeMap1(n - coinTypes.get(indexFrom), coinTypes, 
      indexFrom, memoMap); 
    // memoMap.put(new Tuple(n,indexFrom), leftAns); 

    int rightAns = coinChangeMap1(n, coinTypes, ++indexFrom, memoMap); 
    memoMap.put(new Tuple(n, indexFrom), leftAns + rightAns); 

    return memoMap.get(new Tuple(n, indexFrom)); 
} 

}

我的班級元組是:

public class Tuple { 

    int n; 
int idxFrom; 
public Tuple(int n, int indexFrom) { 
    this.n = n; 
    this.idxFrom = indexFrom; 
} 

@Override 
public boolean equals(Object other){ 
    if(!(other instanceof Tuple)){ 
     return false; 
    } 
    Tuple o = (Tuple)other; 
    return ((this.n == o.n) && (this.idxFrom == o.idxFrom)); 
} 

@Override 
public int hashCode(){ 
    int hashCode = 1; 
    hashCode = 37 * hashCode + this.n + this.idxFrom; 
    return hashCode; 
} 
} 
+1

也許顯示之前有效的代碼,這樣我們可以看到你在重構到記憶中可能出錯的地方 –

回答

0

我不能說這是唯一的問題,但一個問題是indexFrom在兩次遞歸調用之間遞增。在基於數組的版本中,這會導致兩個答案不會相加。散列映射版本一起添加兩個值,但可能會用錯誤的密鑰存儲結果。