零钱兑换

2019-05-21 本文已影响0人最困惑的时候就是能成长的时候

题目地址:https://leetcode-cn.com/problems/coin-change/
题解:

一.思考步骤

1.建模

①解:<x1,x2...xn>代表了Xi代表了第i种硬币的个数
②目标函数:所有金币的价值为总数accout,且数量最少 $min\{\Sigma_{i=1}^nx_i \}$
③约束条件:所有的金币价值为accout $account = \Sigma_{i=1}^nv_ix_i$

2.子问题优化

我使用k种硬币,总数为y,那么k=n,y=account的时候是原问题, $F_k(y)代表了k种硬币,组成y总数时的最小硬币数$
⑴:y>Vk,y>0,k>0

$F_k(y) = min\{F_{k-1}(y),F_k(y-v_k)+1\}$
⑵:y=0或者k=0
$F_k(y) =0$
⑶:y<Vk
$F_k(y) =F_{k-1}(y)$
⑷:y<Vk,且k=1
$F_k(y) =-1$

3.归结公式

$F_k(y) \begin{cases} min\{F_{k-1}(y),F_k(y-v_k)+1\}, &当y>vk,k>0,y>0;\\ 0, &当y=0;\\ F_{k-1}(y),&当y<w_k;\\ ∞,&当k=1,y<w_1或k=0 \end{cases}$

二.伪代码

dp[][]=new int[n+1][account+1]; 代表了k种,y总量的最小硬币数
for i=0 →n+1
   dp[i][0]=0;  //条件二
for j=1 →account+1
   dp[0][j]=∞;  //条件四
for i=1 →n+1
   for j=1 →account+1
      分成三种情况:
      1.如果j>coins[i],那么说明当前至少有一个硬币,dp[i][j]=min(dp[i][j-coins[i]]+1,dp[i-1][j]);
      2.如果j=coins[i],那么说明当前刚好够一个硬币dp[i][j]=1
      3.如果j<coins[i],那么说明当前的第i种硬币面值过大,应该减少,但是如果i=1的话说明只用第一种硬币无法满足条件,也就是dp[1][j]=∞,不等于1的话  dp[i][j]=dp[i-1][j]
最后返回dp[n][account]

三.代码

public int coinChange(int[] coins, int amount) {
        int[][] dp=new int[coins.length+1][amount+1];
        for(int i=0;i<coins.length+1;i++)dp[i][0]=0;
        for(int i=0;i<amount+1;i++)dp[0][i]=Integer.MAX_VALUE;
        for(int i=1;i<coins.length+1;i++){
            for(int j=1;j<amount+1;j++){
                //情况一
                if(j>coins[i-1])dp[i][j]=(dp[i][j-coins[i-1]] ==Integer.MAX_VALUE)?dp[i-1][j]:Math.min(dp[i][j-coins[i-1]]+1,dp[i-1][j]);
                //情况二
                else if(j==coins[i-1])dp[i][j]=1;
                //情况三
                else{
                   if(i==1)dp[i][j]=Integer.MAX_VALUE;
                   else dp[i][j]=dp[i-1][j];
                }
            }
        }
        if(dp[coins.length][amount]==Integer.MAX_VALUE) {
            dp[coins.length][amount]=-1;
        }
        return dp[coins.length][amount];
    }

四:其它写法

public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        dp[0]=0;
        for(int i=1;i<amount+1;i++) {
            dp[i]=Integer.MAX_VALUE;
            for(int j=0;j<coins.length;j++) {
                if(i-coins[j]>=0&&dp[i-coins[j]]+1<dp[i]&&dp[i-coins[j]]!=-1) {
                    dp[i]=dp[i-coins[j]]+1;
                }
            }
            if(dp[i]==Integer.MAX_VALUE) {
                dp[i]=-1;
            }
            
        }
        return dp[amount];
    }

这种就是先去计算dp[i]在使用所有硬币的时候的硬币数,然后到dp[amount]的时候比较各个dp[amount-coins[i]]的关系