322. 零钱兑换(leetcode)

https://leetcode.cn/problems/coin-change/description/

代码上比较麻烦的dp题,由于求的是最少数量,因此求答案时需要初始化无穷大来计算

class Solution {
    public int coinChange(int[] coins, int amount) {
        // f[i][j]表示前i个数中选,体积等于amount的选择最少硬币的数量
        // 以第i个数选多少来划分子集
        // f[i][j] = min(f[i-1][j],f[i][j-coins[i]] + 1) 选的话数量需要+1
        // 初值:f[0][0]=0;凑出0不需要硬币,且为便于计算,将f置为无穷大,只有f[0][0]=0;
        // 给dp数组每个位置赋初值为INT_MAX是为了最后判断是否能填满amount,为了防止溢出,用的MAX_VALUE/2
        // 答案是f[n][amount]

        int n = coins.length;
        int[][] f = new int[15][amount+10];
        for(int i=0;i<n;i++)Arrays.fill(f[i],Integer.MAX_VALUE / 2);
        f[0][0]=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=amount;j++)
            {
                if(j>=coins[i-1])f[i][j]=Math.min(f[i-1][j],f[i][j-coins[i-1]]+1);
                else f[i][j]=f[i-1][j];
            }
        // 判断是否是无解
        return f[n][amount] < Integer.MAX_VALUE / 2 ? f[n][amount] : -1;
    }
}