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

一时失言乱红尘 2022-09-10 12:11 140阅读 0赞

#### 题目 ####

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

对应 [Github 开源项目][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;
        }
    
    }

[Github]: https://github.com/903328615/algorithmic-total-solution