动态规划-鸣人的影分身java

解题思路:这个问题是m拆分成n个数相加，有多少个，考虑n中最小值如果是0，那么答案不变，如果不是0，从1开始一个一个分。

1. 首先考虑多次递归，但是时间复杂度不合适，这里我们用动态规划

2. 我想着用BufferedReader比较方便，我自己不太熟悉这个类的用法，不过这个方法比Scanner更节省，所以就开始学用这个了

   /*
                   f[j][k]的值  (f[0][0]=1)
                   当能量0，分身1，2，3时.都只有一种分法
                   当能量1时,也是1种
                   当能量2时，即能量1时的最大值f[j-k][k]加上现在的最大值f[j][k]
                   为什么现在的最大值是f[j][k] f[j][k]是能量不够分的情况下的，有且只有一个值
                    */

参考代码:

1. import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.Arrays;
   
   public class Main {
      static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      static int N = 11, t, m, n;
      static int[][] f;
   
      public static void Initi() {
          f = new int[N][N];
          for (int i = 0; i < N; i++) {
              Arrays.fill(f[i], 0); //所有元素设为0
          }
          f[0][0] = 1;//0点能量，0分身 =1种
      }
   
      public static void main(String[] args) throws Exception {
          t = Integer.parseInt(br.readLine());
          for (int i = 0; i < t; i++) {
              Initi(); //初始化二位数组
              String s[] = br.readLine().split(" ");
              m = Integer.parseInt(s[0]);
              n = Integer.parseInt(s[1]);
              for (int j = 0; j <= m; j++) { //7
                  for (int k = 1; k <= n; k++) { //3
                      //精髓在这里
                    
                      f[j][k] = f[j][k - 1];
                      if (j >= k) {
                          f[j][k] = f[j][k] + f[j - k][k];
                      }
                  }
              }
              System.out.println(f[m][n]);
          }
   
   
      }
   }