POJ 1664 放苹果(递归或DP)
2024-08-28 23:29:33
一、Description
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
Input
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
Output
对输入的每组数据M和N,用一行输出相应的K。
二、题解
这道题最重要的就是要找到突破口,这个突破口就是把所有的结果分为,有一个盘子为空和全部盘子都有苹果这两种情况。之后再递归求解子问题。
f(m-n,n):每个盘子都有苹果
二、题解
这道题最重要的就是要找到突破口,这个突破口就是把所有的结果分为,有一个盘子为空和全部盘子都有苹果这两种情况。之后再递归求解子问题。
f(m-n,n):每个盘子都有苹果
f(m,n-1):至少有一个盘子没有苹果
则,f[m][n] = f[m-n][n]+f[m][n-1]
这里有详细题解和扩展http://www.cnblogs.com/celia01/archive/2012/02/19/2358673.html
三、Java代码
import java.util.Scanner; public class Main {
public static int f(int a,int b){
if(a<0)
return 0;
if(a==0||b==1)
return 1;
return f(a-b,b)+f(a,b-1);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n=cin.nextInt();
int a,b;
for(int i=0;i<n;i++){
a=cin.nextInt();
b=cin.nextInt();
System.out.println(f(a,b));
}
}
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- 【转】Windows下使用libsvm中的grid.py和easy.py进行参数调优
- C#开源日志Nlog入门
- MySql联接算法
- Centos7安装图形界面
- 需要交互的shell编程——EOF(转载)
- 「Mobile Testing Summit China 2016」 中国移动互联网测试大会-议题征集
- CSS 使用推荐
- F2工作流引擎之 概述(一)
- careercup-排序和查找 11.2
- 对MFC 框架的认识
- mybatis---知识点复习
- OSG世界坐标转屏幕坐标(转载)
- java 日期格式处理
- python结巴(jieba)分词
- django xadmin(1)
- Create and Embed an Application Manifest (UAC)
- [03] JSP指令
- pip 报错
- jacoco初探
- Mysql字符集介绍