Динамическое программирование вопроса о монетах: нисходящий метод запоминания - PullRequest
Новая
       50

Динамическое программирование вопроса о монетах: нисходящий метод запоминания

0 голосов
/ 05 марта 2019

В настоящее время я работаю над вопросом динамического программирования изменения монет на leetcode - https://leetcode.com/problems/coin-change/.

Вот вопрос: 

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

Я пытался реализовать топподход с запоминанием, где я храню массив значений длины, где каждый индекс представляет минимальное количество монет, которое я могу использовать для получения этой суммы.

Вот мой код на Java: 

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        int min = coinChange(coins, amount, dp);

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private int coinChange(int[] coins, int amount, int[] dp) {
        if (amount < 0) {
            return Integer.MAX_VALUE;
        }
        if (amount == 0) {
            return 0;
        }

        if (dp[amount] != Integer.MAX_VALUE) {
            return dp[amount];
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int val = coinChange(coins, amount - coins[i], dp);

            if (val != Integer.MAX_VALUE) {
                min = Math.min(min, val + 1);
            }
        }

        dp[amount] = min;
        return min;
    }
}

Я думал, что это правильный подход к динамическому программированию для этой проблемы, однако я получаю ограничение по времени для leetcode.

Это неправильный подход к динамическому программированию?Если да, то можете ли вы объяснить, где это не так?

Заранее большое спасибо.

...