leetcode 322 之记忆化搜索？

来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum

triump

2018-11-14

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 是否放在背包里的分情况处理么？

写回答

2回答

triump

提问者

2018-11-15

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;
        }
    }
}

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

triump

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

2018-11-16

共2条回复