AOJ1209 Square Coins

問題リンク Square Coins

• 概要

1, 4, 9, ..., 289(=17^2) の価値のお金がある。これらの硬貨を使ってN円を払う方法は何通りあるかを答えよ。
N < 300

• 解法

DPです。
dp[i][j]: i^2までの硬貨を使ってj円を表せる組み合わせ数
の表を作るだけです。

• ソース

import java.util.Scanner;

//Square Coins
public class AOJ1209 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int[][] dp = new int[18][300];
		dp[0][0]=1;
		for(int i=1;i<18;i++){
			int x = i*i;
			for(int j=0;j<300;j++){
				if(j-x>=0)dp[i][j]=dp[i][j-x];
				dp[i][j] += dp[i-1][j];
			}
		}
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			System.out.println(dp[17][n]);
		}
	}

	public static void main(String[] args) {
		new AOJ1209().run();
	}
}