Leetcode для размена монет

Вам дан целочисленный массив coins, представляющий монеты разного номинала, и целое число amount, представляющее общую сумму денег.

Верните наименьшее количество монет, которое необходимо для получения этой суммы. Если сумма денег не может быть получена ни одной комбинацией монет, верните -1.

Вы можете считать, что у вас бесконечное количество монет каждого вида.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Вход в полноэкранный режим Выход из полноэкранного режима
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount ==0) return 0;
        // we will use dynamic prgramming for  solving this 
        // bottom-up approach
        int dp[][] = new int[coins.length][amount+1];
        for(int row[]: dp) Arrays.fill(row,-1);
        // we will start from last index and go to first index
        int coinsNeeded = findSmallestList(coins.length-1,coins,amount,dp);
        return coinsNeeded ==(int)1e9 ? -1 : coinsNeeded;
    }
    public int findSmallestList(int index,int[] coin,int amount,int dp[][]){
       if(index==0){
           if(amount % coin[index] ==0){
               return amount/coin[index];
           }
           return (int)1e9;
       }
      if(dp[index][amount]!=-1) return dp[index][amount];

        int left =(int)1e9;
        //take same index value
        if(amount>=coin[index]){
            left = 1+ findSmallestList(index,coin,amount-coin[index],dp);
        }
        //take next index 
        int right = 0+ findSmallestList(index-1,coin,amount,dp);
        //System.out.println(Integer.min(left,right));
        return dp[index][amount] =Integer.min(left,right); 
    }
}
Войти в полноэкранный режим Выход из полноэкранного режима

Мы можем удалить пространство стека, используя подход сверху вниз, т.е. подход табуляции Dp

Оцените статью
devanswers.ru
Добавить комментарий