硬币组合问题

问题描述：
有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();
    }
}

动态规划太头疼了，代码实现太复杂。