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)
  • コード実装
    再帰
    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];
    }