首页 > 专题系列 > Java解POJ > POJ 1664 放苹果 [解题报告] Java
2013
11-10

POJ 1664 放苹果 [解题报告] Java

放苹果

问题描述 :

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

输入:

第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。

输出:

对输入的每组数据M和N,用一行输出相应的K。

样例输入:

1
7 3

样例输出:

8

解题代码:

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 *
 *poj1664
 * f(m, n) = f(m-n, n) + f(m, n-1)
 * f(m, n): 把m个苹果放到n个盘子中的方法数
 * f(m, n-1): 把m个苹果放到n-1个盘子中的方法数(其中至少有一个空盘子)
 * f(m-n, n): 把m个苹果放到n个盘子中,而且每个盘子中都有苹果(先拿n个出来,等m-n个放好了,然后每个盘子放一个)
 * @author NC
 */
public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        if (scan.hasNext()) {
            int n = scan.nextInt();
            for (int i = 0; i < n; i++) {
                int a = scan.nextInt();
                int b = scan.nextInt();
                System.out.println(f(a, b));
            }
        }
    }

    static int f(int m, int n) {
        /* 有些盘子不放苹果,已包含在f(m, n - 1)中,返回0*/
        if (m < 0) {
            return 0;
        }
        /* 刚好每个盘子放1个,只有一种情况 */
        if (m == 0) {
            return 1;
        }
        /* 只有1个盘子可以放,也只有全部放入这一种情况 */
        if (n == 1) {
            return 1;
        }
        /* n个盘子内至少都放1个 + 只放入n-1个盘子中 */
        return f(m - n, n) + f(m, n - 1);
    }
}

  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环