package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月18日 22:07
 * @description: 力扣322 零钱兑换
 */
public class CoinChange {
 public static void main(String[] args) {
 Scanner sr = new Scanner(System.in);
 int amount = sr.nextInt();
 sr.nextLine();

 String []str = sr.nextLine().split(" ");
 int [] coins = new int[str.length];
 for(int i = 0;i < str.length;i++){
 coins[i] = Integer.valueOf(str[i]);
 }
 int ans = new ConinChange_Solution().coinChange(coins,amount);
 System.out.println(ans);
 }
}
class ConinChange_Solution{

 public int coinChange(int[] coins, int amount) {

 int []dp = new int[amount+1]; //dp[i] 表示金额之和等于i的硬币组合数,
 dp[0] = 1; //只有当不选取任何硬币时,金额之和才为0,因此只有1种硬币组合

 //对于面额为coin的硬币,当coin <= i <= amount时,如果存在一种硬币组合金额之和等于i-coin ,则在该硬币
 //组合中增加一个面额为coin的硬币,即可得到一种金额之和等于i的硬币的组合,因此需要遍历coins,对于其中的每一种面额的硬币,
 //更新dp数组中的每个大于或等于该面额的元素的值。
 for(int coin :coins){
 for(int i = coin; i<=amount;i++){
 dp[i] += dp[i - coin]; //dp[i]可能会随着coin的遍历,累加很多次
 }
 }
 return dp[amount];
 }
}