（Java实现）洛谷 P1025 数的划分

题目描述

将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5;

1,5,1;

5,1,1.

问有多少种不同的分法。

输入输出格式

输入格式：

n,k (6<n≤200，2≤k≤6)

输出格式：

1个整数，即不同的分法。

输入输出样例

输入样例#1：

7 3

输出样例#1：

4

说明

四种分法为：

1,1,5;

1,2,4;

1,3,3;

2,2,3.

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class shudehuafen {

	 public static void main(String[] args) throws IOException {

	        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

	        String[] s = reader.readLine().split(" ");

	        int n = Integer.parseInt(s[0]);

	        int k = Integer.parseInt(s[1]);

	        int dp[][] = new int[n+1][k+1];

	        //dp[i][j]表示将i分成j份的方法种数

	        //初始化:当i=j或j=1的时候,则只有一种分法;

	        for (int i = 1; i <=n; i++) {

	            dp[i][1] = 1;

	        }

	        //当i>j时,我们可以转化为   有1的情况+没有1的情况

	        //(1)当i>j时  则有dp[i][j] = dp[i-1][j-1]+dp[i-j][j];

	        //(2)当i=j时 则有1种分法

	        //(2)当i<j时 则有0种分法

	        for (int i = 1; i <=n; i++) {

	            for (int j = 1; j <=k; j++) {

	                if (i==j)dp[i][j] = 1;

	                if (i>j)dp[i][j] = dp[i-1][j-1]+dp[i-j][j];

	            }

	        }

	        System.out.println(dp[n][k]);

	    }

}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Scanner;

public class Demo3n分m {

	public static void main(String[] args) throws IOException {

		   BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

	        String[] s = reader.readLine().split(" ");

	        reader.close();

	        int n = Integer.parseInt(s[0]);

	        int m = Integer.parseInt(s[1]);

	        int dp[][] = new int[n+1][m+1];

		dp[1][1]=1;

		for (int i = 2; i <=n; i++) {

			for (int j = 1; j <= Math.min(i, m); j++) {

				dp[i][j]=dp[i-1][j-1]+dp[i-j][j];

			}

		}

		System.out.println(dp[n][m]);

	}

}

import java.util.Scanner;

public class Demo3n分m {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int m = sc.nextInt();

		sc.close();

		int [] [] num = new int [n+1][m+1];

		num[1][1]=1;

		for (int i = 2; i <=n; i++) {

			for (int j = 1; j <= Math.min(i, m); j++) {

				num[i][j]=num[i-1][j-1]+num[i-j][j];

			}

		}

		System.out.println(num[n][m]);

	}

}

巴特西

（Java实现）洛谷 P1025 数的划分

最新文章

热门文章

巴特西

（Java实现） 洛谷 P1025 数的划分

最新文章

热门文章

（Java实现）洛谷 P1025 数的划分