m個のりんごをn個のかごに入れる(java)
8353 ワード
タイトルの説明
既存m個の同じリンゴ(00)があって、かごを空にすることを許可して、何種類の置き方がありますか?(注:1 3 1と1 3は一種の置き方です)
例:入力7 3出力8
テーマ分析
テーマはn>mとn<=mの2つに分けることができます. n>mこのときかごの数はリンゴの数より大きく、かごは同じであるため、このとき同じm個のかご、すなわち、F(m,n)=F(m,m)F(m,n)=F(m,m)F(m,n)=F(m,m) n<=mこのときかごの数がリンゴの木に等しいより小さく、かごが空であることから、(1)少なくとも1つのかごが空である、すなわち、F(m,n)=F(m,n−1)F(m,n)=F(m,n)=F(m,n−1)F(m,n)=F(m,n)=F(m,n)=F(m,n−−1)(2)かごにリンゴがあり、かごごとにリンゴがあれば、かごごとに1つずつリンゴを取り出し、結果には影響しないので,F(m,n)=F(m−n,n)F(m,n)=F(m−n,n)F(m,n)=F(m,n)=F(m−n,n) コード実装
再帰
ダイナミックプランニング
既存m個の同じリンゴ(00)があって、かごを空にすることを許可して、何種類の置き方がありますか?(注:1 3 1と1 3は一種の置き方です)
例:入力7 3出力8
テーマ分析
テーマはn>mとn<=mの2つに分けることができます.
再帰
private static int digui(int m, int n) {
//
// 1 , 1
if (m == 0 || n == 1) {
return 1;
}
if (n > m) {
return digui(m, m);
} else {
return digui(m, n-1) + digui(m-n, n);
}
}
ダイナミックプランニング
private static int dp(int m, int n) {
//
int[][] resultTable = new int[m+1][n+1];
for (int j = 1; j <= n; j++) {
//
resultTable[0][j] = 1;
}
for (int i = 1; i <= m; i++) {
//
resultTable[i][1] = 1;
}
// i ,j
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j > i) {
resultTable[i][j] = resultTable[i][i];
} else {
resultTable[i][j] = resultTable[i][j-1] + resultTable[i-j][j];
}
}
}
return resultTable[m][n];
}