POJ1664 메모리 귀환, 간단하고 알기 쉽다
1066 단어 私人
public class DivideApple3 {
static long[][] results;
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
results=new long[10001][11];
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
sc = new Scanner(new File("files/apple"));
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
int m = sc.nextInt();
int n = sc.nextInt();
System.out.println(DFS(m, n));
}
}
private static long DFS(int m, int n) {
// TODO Auto-generated method stub
if (m == 0 || n == 1)
return 1;
if(results[m][n]!=0)
return results[m][n];
for (int i = 0; i <= m / n; i++) {
results[m][n] += DFS(m - i * n, n - 1);
}
return results[m][n];
}
}
sample input: 6 7 3 10 5 2 1 30 2 1000 10 10000 10
sample output: 8 30 1 16 968356321790171 3016757406431865393