Memoizationテーブルが動作しない

Question

私は、memoizationコードが正常に動作しています。これは、 'n'がm個の可能な値で表現できる方法の数を計算します。しかし、以下のコードでは、memoizationテーブルのmemoNMが答えではなく0を返しているのは242です。この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; 
} 
} 

Answer 1

私は、これが唯一の問題であると言うことはできないが、 1つの問題は、indexFromが2つの再帰呼び出しの間でインクリメントされていることです。配列ベースのバージョンでは、2つの答えが一緒に追加されません。ハッシュマップバージョンは2つの値を加算しますが、間違ったキーで結果を格納する可能性があります。