动态规划B最值问题

接下来用一道例题来认识动态规划的最值问题，首先声明一下，这些题可能有其他解法，但在这里我只是说一说关于动态规划的解法。

开始吧！

322. 零钱兑换

题目地址

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例1： >输入：coins = [1, 2, 5], amount = 11
>输出：3
>解释：11 = 5 + 5 + 1

示例2： >输入：coins = [2], amount = 3
>输出：-1

示例3： >输入：coins = [1], amount = 0
>输出：0

示例4： >输入：coins = [1], amount = 1
>输出：1

示例5： >输入：coins = [1], amount = 2
>输出：2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= \(2^{31}\) - 1
• 0 <= amount <= \(10^4\)

begin

题目描述得很清楚了，你是否有了想法，建议先尝试一下，考虑用动态规划怎么解。

动态规划

A 计数问题 B 最值问题 C 可行性问题

一、确定状态

1. 最后一步
2. 子问题

二、转移方程

三、初始条件和边界问题

初始条件：用转移方程算不出来，需要手工定义
边界情况：数组不能越界

四、计算顺序

B最值问题

很明显这是一个关于最值的问题，题目要求解的是用最少的硬币组成目标数字，如果没有这样的解就返回-1。题目让求的仅仅是最少需要几个硬币，而不是要求这最少的那些组合是什么，这就是动态规划的一个标志吧，不要过程要结果。

按照上面的顺序来：

一、确定状态

1. 最后一步

我们假设有这么最后一块硬币使我们组成了目标数字，并且这就是最少组合，如我们要凑出n，那么我们设最少方案是a1,a2,...ak,组成了n。那么我们的最后一块就是ak，前面则是a1-ak-1组成了n-ak，并且他们都是最少方案。

2. 子问题

根据最后一步，我们把由k块硬币组成n的问题变成了由k-1块组成n-ak的问题，很明显是将一个大问题变成一个规模更小的问题了，所以这个就是子问题。

二、转移方程

我们设f(n)表示组成n的最少个数，那么f(n)=min(f(n-ak1)+1,f(n-ak2)+1)，这里的ak1、ak2代表的是所有可能的硬币，例如我们要组成27，并且我们只有2、5、7三种硬币，f(27)=min(f(27-2)+1,f(27-5)+1,f(27-7)+1)，这就是我们的转移方程。

三、初始条件和边界问题

我们可以用数组来保存小于等于n的最少个数，这时候我们要确认用转移方程算不出来，需要手工定义的初始条件，关于这个题是f(0)=0,之后当然还要考虑数组边界问题。

四、计算顺序

关于这个题的计算顺序还是比较清晰的，我们并需要从小到大逐个计算，最后得到f(n)。

一种java题解

class Solution {
    public int coinChange(int[] coins, int amount) {
        int A=coins.length;
        int max=amount+1;
        int[] f=new int[amount+1];
        Arrays.fill(f,max);
        f[0]=0;

        for(int i=1;i<=amount;i++){
            for(int j=0;j<A;j++){
                if(i>=coins[j]){
                    f[i]=Math.min(f[i],f[i-coins[j]]+1);
                }
            }
        }
        return f[amount]>amount? -1:f[amount];
    }
}

这个题解还是做了很好处理的，就在那个“int[] f=new int[amount+1];”这样在最后就可以比较amount直接确定结果了。

详细题解

推荐视频

动态规划入门