Aizu Online Judge 1209 Square Coins

■1209 Square Coins

dp[i]を支払う金額がiの時のコインの組み合わせの数とする．
コインa[0],…,a[j-1]までのdp[i]が求められていれば，a[j]についてのdp[i]を以下の式で更新すれば良い．
dp[i]+=dp[i-a[j]]

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  void run(){  
17.   int n=17;  
18.   int[] a=new int[n];  
19.   for(int i=0; i<n; i++){  
20.    a[i]=(i+1)*(i+1);  
21.   }  
22.   int max=300;  
23.   int[] dp=new int[max];  
24.   dp[0]=1;  
25.   for(int j=0; j<n; j++){  
26.    for(int i=a[j]; i<max; i++){  
27.     dp[i]+=dp[i-a[j]];  
28.    }  
29.   }  
30.   for(;;){  
31.    int k=sc.nextInt();  
32.    if(k==0){  
33.     break;  
34.    }  
35.    println(""+dp[k]);  
36.   }  
37.  }  
38.   
39.  void debug(Object... os){  
40.   System.err.println(Arrays.deepToString(os));  
41.  }  
42.   
43.  void print(String s){  
44.   System.out.print(s);  
45.  }  
46.   
47.  void println(String s){  
48.   System.out.println(s);  
49.  }  
50.   
51.  public static void main(String[] args){  
52.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
53.   new Main().run();  
54.  }  
55. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int n=17;
  int[] a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=(i+1)*(i+1);
  }
  int max=300;
  int[] dp=new int[max];
  dp[0]=1;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<max; i++){
    dp[i]+=dp[i-a[j]];
   }
  }
  for(;;){
   int k=sc.nextInt();
   if(k==0){
    break;
   }
   println(""+dp[k]);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}