首页 > 试题广场 >

硬币划分

[编程题]硬币划分
  • 热度指数:2058 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱(n <= 100000),有多少中组合可以组成n分钱?

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


输出描述:
输出组合数,答案对1e9+7取模。
示例1

输入

13

输出

16
状态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)