放苹果

[编程题]放苹果

热度指数：10727 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：5、1、1 和 1、5、1 是同一种分法，即顺序无关。

输入描述:

输入包含多组数据。

每组数据包含两个正整数 m和n（1≤m, n≤20）。

输出描述:

对应每组数据，输出一个整数k，表示有k种不同的分法。

示例1

输入

7 3

输出

算法知识视频讲解

Java

骄阳似我

import java.util.Scanner;

public class Main {
    public static void main(String[]args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int m = scan.nextInt();
            int n = scan.nextInt();
            int [][] dp = new int[m+1][n+1];
            for(int j=1;j<=n;j++) {
                dp[0][j] = 1;
                dp[1][j] = 1;
            }
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    if(j<=i){//苹果比盘子多
                        dp[i][j] = dp[i][j-1] + dp[i-j][j];
                    }else{//苹果比盘子少
                        dp[i][j] = dp[i][i];
                    }
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}

编辑于 2017-09-01 20:15:04 回复(0)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			System.out.println(fun(m, n));
		}
	}
	public static int fun(int m, int n) {
		if(m == 0 || n == 1) return 1;
		if(n > m) return fun(m, m);
		else return fun(m, n - 1) + fun(m - n, n);
	}
}

发表于 2016-10-15 16:50:18 回复(0)