信息学奥赛一本通T1440-数的划分

解题思路:

dfs简单使用。其中，需要对划分做一些简单处理，即升序划分。

注意事项:

本题解没有对dfs进行优化，时间复杂度较高，但是能过oj。

参考代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
   static int k = 0;
   static int n = 0;
   static int res = 0;

   public static void main(String[] args) throws IOException {
      BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
      String[] s = reader.readLine().split(" ");
      n = Integer.parseInt(s[0]);//整数n
      k = Integer.parseInt(s[1]);//被分成k份
      if (n == 0 || k == 0 || n < k)
         return;
      dfs(0,0,1);
      System.out.println(res);
   }

   /**
    * @param sum   所分数之和
    * @param cnt   所分成数的个数
    * @param start 起始数（升序划分）
    */
   static void dfs(int sum, int cnt, int start) {
      //cnt == k 时判断是否所划分的数为n
      if (cnt == k) {
         if (sum == n) {
            res++;
         }
         return;
      }
      //sum大于n时直接返回
      if (sum > n) {
         return;
      }
      for (int i = start; n - sum >= i * (k - cnt); i++) {
         dfs(sum+i,cnt+1,i);
      }
   }
}