Memoization表不工作

Question

我已经让非记忆化代码正常工作了，它计算了在给定m个可能的值的情况下，'n‘可以表示的方式的数量。但是在下面的代码中，我不明白为什么记忆表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));
}

}

我的类Tuple是：

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

我不能说这是唯一的问题，但有一个问题是indexFrom在两次递归调用之间递增。在基于数组的版本中，这会导致两个答案不能相加。hashmap版本将两个值相加，但很可能使用错误的键存储结果。