AcWing 1050. 鸣人的影分身
原题链接
中等
作者:
Azir12138
,
2021-03-12 22:13:28
,
所有人可见
,
阅读 341
看注解
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T-- > 0) {
int m = sc.nextInt();
int n = sc.nextInt();
int max = Math.max(n, m);
int[][] dp = new int[max][max];
for(int i = 0; i < max; i++) { //i为查克拉,j为分身
for(int j = 0; j < max; j++) {
if(i == 0) { //当查克拉为0时,分身只有一种。
dp[i][j] = 1;
}else if(j == 0) {//当分身为0时,分不了。
dp[i][j] = 0;
}else if(i < j) {//当查克拉小于分身,必然会有(j-i)个分身没有查克拉。
dp[i][j] = dp[i][i];
}else {
dp[i][j] = dp[i][j - 1] + dp[i - j][j];//查克拉大于分身,两种情况。
//1、其中一个分身没有查克拉(依次递归下去)----dp[i][j-1]。
//2、已经给每一个分身分配好一个查克拉。
}
}
}
System.out.println(dp[m][n]);
}
sc.close();
}