【中等】拼 M 面值硬币问题（动态规划）-蒲公英云

【中等】拼 M 面值硬币问题（动态规划）

题目

现在有 n1 + n2 种面值的硬币，n1 种为普通面值硬币，可以随意取用。n2 种为纪念币，每种最多只能取一个。每种硬币有一个面值，问：凑满 M 面值有多少种取法？

对应 Github 开源项目 class common.Question1

盲题思路：

数据结构：HashMap
方法：循环 + 条件判断
以 n2 作为突破口，不取 n2 和，取所有可能的 n2
先排序。

开题解法：

数据结构：数组
动态规划，两个动规数组，不需要排序
dp 含义 dp[i][j] 使用 0-i 种的普通硬币恰好凑满 j 的取法
对于普通货币数组 arr[i]
动态转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]]
看最后一行
对于纪念币数组 brr[i]
动态转移方程 dp[i][j] = dp[i-1][j] + dp[i-1][j-brr[i]]
看最后一行
最后计算总的凑法则为两边 dp 钱数互补相乘

解法思路小结

首先从题面来看，需要先进行【可能性推断假设】，在【盲题推断】中，就是因为可能性推断假设没有充分所以有这样不成熟的思路（其实在考虑的时候就觉得不太靠谱）。

动态规划问题，为什么能想到动态规划？
不妨做个假设，或者排除法，取法问题优先考虑是否可以使用动态规划求解。
这个假设先放在这里，在后续的题目中进行验证。

题解

/** * @program: algorithmic-total-solution * @description: 拼 M 面值硬币方法（动态规划问题） * 现在有 n1 + n2 种面值的硬币，n1 种为普通面值硬币，可以随意取用。n2 种为纪念币，每种最多只能取一个。 * 每种硬币有一个面值，问：凑满 M 面值有多少种取法？ * @author: wangzibin **/
public class Question1 { 
    public static void main(String[] args) { 
        int[] arrCommon = new int[]{ };
        int[] arrSpecial = new int[]{ 1,2,5,6,7};
        int targetMoney = 30;
        long num=getMargeMoneyNum(arrCommon, arrSpecial, targetMoney);
        System.out.println("共有 "+num+" 种凑法");
    }
    private static long getMargeMoneyNum(int[] arrCommon, int[] arrSpecial, int targetMoney) { 
        int[][] dpCommon = getCoinCommonDp(arrCommon, targetMoney);
        int[][] dpSpecial = getCoinSpecialDp(arrSpecial, targetMoney);
        // 边界检测
        if (dpCommon == null && dpSpecial == null) { 
            return targetMoney == 0 ? 1 : 0;
        } else if (dpCommon == null) { 
            return dpSpecial[dpSpecial.length - 1][targetMoney];
        } else if (dpSpecial == null) { 
            return dpCommon[dpCommon.length - 1][targetMoney];
        }
        long num = 0;
        for (int i = 0; i <= targetMoney; i++) { 
            num += (long) dpCommon[arrCommon.length - 1][i] * dpSpecial[arrSpecial.length - 1][targetMoney - i];
        }
        return num;
    }
    /** * 普通硬币 dp 表构建 */
    public static int[][] getCoinCommonDp(int[] arr, int target) { 
        if (arr == null || arr.length < 1) { 
            return null;
        }
        int[][] dp = new int[arr.length][target + 1];
        for (int i = 0; i < arr.length; i++) { 
            //初始化第一列 凑 0 元
            dp[i][0] = 1;
        }
        for (int j = arr[0]; j < target + 1; j = j + arr[0]) { 
            //初始化第一行
            dp[0][j] = 1;
        }
        // 动态转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]]
        for (int i = 1; i < arr.length; i++) { 
            for (int j = 1; j < target + 1; j++) { 
                dp[i][j] = dp[i - 1][j];
                int jp = j - arr[i];
                dp[i][j] += jp >= 0 ? dp[i][jp] : 0;
            }
        }
        return dp;
    }
    /** * 纪念币 dp 表构建 */
    public static int[][] getCoinSpecialDp(int[] arr, int target) { 
        if (arr == null || arr.length < 1) { 
            return null;
        }
        int[][] dp = new int[arr.length][target + 1];
        for (int i = 0; i < arr.length; i++) { 
            //初始化第一列 凑 0 元
            dp[i][0] = 1;
        }
        // 纪念币只能用一个
        if (arr[0] <= target) { 
            dp[0][arr[0]] = 1;
        }
        // 动态转移方程 dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]]
        for (int i = 1; i < arr.length; i++) { 
            for (int j = 1; j < target + 1; j++) { 
                dp[i][j] = dp[i - 1][j];
                int jp = j - arr[i];
                dp[i][j] += jp >= 0 ? dp[i - 1][jp] : 0;
            }
        }
        return dp;
    }
}