如何将Coin Change II的回溯代码转为带记忆化的自上而下递归版本？

问题描述 #

给定不同面额的硬币数组coins和总金额amount，返回组成该金额的组合数，硬币可无限使用，无法组成则返回0，结果保证在32位有符号整数范围内。

初始回溯解法（逻辑正确但超时） #

我采用回溯思路：每个硬币有两种选择，不选则索引+1，选则金额减去该硬币值且索引不变（可重复选取）。代码如下：

class Solution {
    private int count = 0;

    public int change( int amount, int[] coins) {
        Integer[] arr = Arrays.stream( coins)
                                .boxed()
                                .sorted( Comparator.reverseOrder())
                                .toArray( Integer[]::new);
        backtrack( arr, 0, amount);
        return count;
    }

    private void backtrack( Integer[] coins, int index, int amount) {
        if( index >= coins.length) {
            if( amount == 0) {
                ++count;
            }
        }
        else { // At every coin we have only two choices, 
               // either we take it or we skip it.
            backtrack( coins, index + 1, amount); 
               // This is the skip case, we are incrementing the index
               // by 1. And not taking that coin value into account
               // by not decrementing the current coin value from amount.
            if( coins[index] <= amount)
              backtrack( coins, index, amount - coins[index]);
               // We are taking that coin and subtracting the coin from the
               // amount, not incrementing the index as the same coin can be
               // considered multiple times, so as to be able to consider
               // it multiple times we are not incrementing the index.
        }
    }
}

该解法逻辑正确，但因递归次数过多导致超时（TLE）。

失败的记忆化递归尝试 #

我尝试将其转为带记忆化的自上而下递归版本，但未成功，尝试代码如下：

class Solution {
    private int count = 0;

    public int change(int amount, int[] coins) {
        int[] memo = new int[amount + 1];
        Arrays.fill( memo, -1);
        backtrack( coins, 0, memo, amount);
        System.out.println( "The content of the array is "
                            + Arrays.toString(memo));
        return memo[amount];
    }

    private void backtrack( int[] coins, int index, int[] memo, int amount) {
        if (index >= coins.length) {
            if (amount == 0) {
                ++count;
                return;
            }
        } else if (memo[amount] != -1){
            return;
        } else {
            backtrack( coins, index + 1, memo, amount);
            if (amount <= coins[index])
              backtrack( coins, index + 1, memo, amount - coins[index]);
            System.out.println( "The value of the count is ---> " 
                    + count 
                    + " and the value of the index is " + index);
            System.out.println( "The content of the array in backtrack is " 
                    + Arrays.toString( memo));  
            memo[amount] += count;  
        }
    }
}

需求 #

• 保留全局count变量、返回值为void的回溯方法模板，通过最小修改使代码返回正确结果。
• 了解从回溯到记忆化递归再到自下而上动态规划的完整演进步骤。

内容的提问来源于stack exchange，提问作者John Doe