leetcode 322 之记忆化搜索？

Question

int search(const vector& coins, int amount){

    if(amount == 0)
        return 0;

    if(dp[amount] != -1)
        return dp[amount];

    int res = max_amount;
    for(int coin: coins)
        if(amount - coin >= 0)
            res = min(res, 1 + search(coins, amount -coin));
    return dp[amount] = res;
}

老师：按照0-1 完全背包，递推关系应该为：dp[i] = min(dp[i], dp[i - coins[j]] + 1) 
 而这个记忆化搜索的递推关系怎么理解？ 这里的for 循环是 依次考虑从第0 个 coin 到第最后一个coin 是否放在背包里的分情况处理么？ 

Answer 1

提问者 triump 2018-11-15 21:22:55

class Solution {
    private static int[][] result;

    private static int maxValue = 100000000;
    public int search(int index, int amount, int[] coins){
        if(index >= coins.length){
            return maxValue;
        }

        if(amount == 0){
            return 0;
        }

        if(amount < 0){
            return maxValue;
        }

       if(result[index][amount] >= 0){
            return result[index][amount];
        }

        result[index][amount] = Math.min(search(index, amount - coins[index], coins) + 1,
                        search(index + 1, amount, coins));
        return result[index][amount];
    }

public int coinChange(int[] coins, int amount) {
        result = new int[20][10000];
        for(int i = 0;i < 20; i++){
            for(int j = 0; j < 10000; j++){
                result[i][j] = -1;
            }
        }

        int val = search(0, amount, coins);
        if(val < maxValue){
            return val;
        }else{
            return -1;
        }
    }
}

上面这段代码也没有问题吧？时间复杂度要低一点。

• liuyubobobo #1

  能ac就没有问题，如果想和我探讨算法思想的话，请结合文字描述你的算法思想，不要只贴代码：）

• 提问者 triump #2

  老师，你的记忆化搜索中的算法思想我的理解是：类似于Integer Break 中的思想，就是依次用给定面值的硬币来对amount 进行切分，用了一个for 循环。这种思想肯定是不会漏掉解，但可能会考虑很多重复的情况，时间复杂度会高点。
  另外一种解法是：可以按照完全背包的思路，考虑第index个硬币 是否放入重量为amount的背包：Math.min(search(index, amount - coins[index], coins) + 1, search(index + 1, amount, coins))
  不知道我理解的对不？

Answer 2

liuyubobobo 2018-11-14 22:24:52

dp[amount] 表示要凑 amount 这么多钱，至少需要多少个硬币。

for 循环是考虑每一种面值的硬币：

对于每一面值coin，如果使用1个这个面值硬币以后，再凑amount - coin这么多钱所需要的最少硬币数 + 1，就是总硬币数。

找到所有可能的总硬币数的最小值。

加油！：）