换钱的方法数

• 题目：给定数组arr，arr中所有的值都为正数，每个值钱的面值，再给定一个整数aim代表要找的钱数，求组成aim的所有方法
• 解答：

  • 空间压缩：将原要使用的二维数组压缩称为一维数组

  • 考虑：

    • 初始值的设置：对于第一个钱最多可以使用次数采用是否可以使用作为初始值

  • 这是对于数组内的钱可以无限使用的情况：

    import java.util.*;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String mn = scanner.nextLine();
            Integer N = Integer.valueOf(mn);
            int []base = {3,5,6,12,4,2};
            System.out.println(getMinCoinOne(base,N));
        }
    
        private static int getMinCoinOne(int[] base, Integer n) {
            int length = base.length;
            // helper[i + 1]表示目标为i+1块钱的值
            int []helper = new int[n + 1];
            for (int j = 0; base[0]*j <= n; j ++){
                // 等于 0 的时候也是一种情况
                helper[base[0]*j] = 1;
            }
            // 从第二个钱开始
            for (int i = 1 ; i < length; i ++){
                for (int j = 1; j <= n; j ++){
                    helper[j] += j - base[i] < 0 ? 0 : helper[j - base[i]];
                }
            }
            return helper[n];
        }
    
    }
    

  
  
  
  
  * 出现了钱币钱数限制的时候：这个时候不适合使用**压缩空间**的方式：
      * 对于使用了**压缩空间**的方式对于单张钱币使用次数无法进行计算
      * 而使用二维数组：可以探寻限制情况
          
          `不用moneys[i], 只用moneys[0~i-1]组成j，此时方法数是dp[i-1][j]
  <3.2> 用一张moneys[i], 且用moneys[0~i-1]组成j-1*moneys[i]，此时方法数是dp[i-1][j-1*moneys[i]]
  <3.3> 用两张moneys[i], 且用moneys[0~i-1]组成j-2*moneys[i]，此时方法数是dp[i-1][j-2*moneys[i]]
  <3.4> 用三张moneys[i], 且用moneys[0~i-1]组成j-3*moneys[i]，此时方法数是dp[i-1][j-3*moneys[i]]`