问题描述:
有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱(n <= 100000),有多少中组合可以组成n分钱?
蛮力发解决(穷举)
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int n1=0,n2=0,n5=0,n10=0 ; int sumary=0; for(n1=0;n1<num+1;n1++){ for(n2=0;n2<(num+1)/2;n2++){ for(n5=0;n5<(num+1)/5;n5++){ for(n10=0;n10<(num+1)/10;n10++){ if(n1+2*n2+5*n5+10*n10==num){ sumary++; } } } } } System.out.println(sumary); sc.close(); } }
动态规划太头疼了,代码实现太复杂。