硬币划分

[编程题]硬币划分

热度指数：2058 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？

输入描述:

输入整数n.(1<=n<=100000)

输出描述:

输出组合数，答案对1e9+7取模。

示例1

输入

输出

算法知识视频讲解

Java

来学习的小张

状态F(i,j) :前i种硬币组成j的方法个数

转移方程：F(i,j): F(i - 1,j) + F(i,j - coins[i - 1]);

初始状态：F(i,0) = 1; F(0,j) = 0;

返回：F(coins,size(),n)

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = {1,2,5,10};
        int[][] methodNum = new int[arr.length + 1][n + 1];
        for(int i = 0;i <= arr.length;i++){
            methodNum[i][0] = 1;
        }
        for(int i = 1;i <= arr.length;i++){
            for(int j = 0;j <= n;j++){
                if(j >= arr[i - 1]){
                    methodNum[i][j] = (methodNum[i - 1][j] + methodNum[i][j - arr[i - 1]]) % 1000000007;
                }else{
                     methodNum[i][j] = methodNum[i - 1][j];
                }
            }
        }
        System.out.println(methodNum[arr.length][n]);
    }
}

发表于 2022-04-08 15:48:58 回复(0)