POJ 1664 放苹果(递归或DP)

时间:2022-09-16 08:46:32

一、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-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));
}
}
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

POJ 1664 放苹果(递归或DP)的更多相关文章

  1. poj 1664 放苹果 递归

    题目链接: http://poj.org/problem?id=1664 题目描述: 有n个苹果,m个盒子,盒子和苹果都没有顺序,盒子可以为空,问:有多少种放置方式? 解题思路: 当前有n个苹果,m个 ...

  2. poj 1664 放苹果(递推)

    题目链接:http://poj.org/problem? id=1664 放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions ...

  3. poj 1664放苹果(递归)

    放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 37377   Accepted: 23016 Description ...

  4. POJ 1664 放苹果 (递推思想)

    原题链接:http://poj.org/problem?id=1664 思路:苹果m个,盘子n个.假设 f ( m , n ) 代表 m 个苹果,n个盘子有 f ( m , n ) 种放法. 根据 n ...

  5. POJ 1664 放苹果

    放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 24985   Accepted: 15908 Description ...

  6. poj 1664 放苹果 &lpar;划分数&rpar;

    题意:中文题目,不解释... 题解: 第一种方法是暴力深搜:枚举盘子1~n放苹果数量的所有情况,不需要剪枝:将每次枚举的情况,即每个盘的苹果数量,以字典序排序,然后存进set里 以此去重像" ...

  7. poj 1664 放苹果(dfs&rpar;

    放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 30284   Accepted: 19098 Description ...

  8. poj 1664 放苹果,递归(深度优先搜索)

    #include "stdio.h" int DFS(int n,int m); int main() { int T; int n,m; int s; scanf("% ...

  9. poj 1664放苹果&lpar;转载&comma;不详细&comma;勿点&rpar;&lpar;递归&rpar;

    题目和别人的解析传送门 我的代码 #include<bits/stdc++.h> using namespace std; int f(int m,int n) { ) ; ||m==) ...

随机推荐

  1. iOS开发Facebook POP动效库使用教程

    如果说Origami这款动效原型工具是Facebook Paper的幕后功臣,那么POP便是Origami的地基.感谢Facebook开源了POP动效库,让人人都能制作出华丽的动效.我们只需5步,便能 ...

  2. &lbrack;LeetCode&rsqb; Sudoku Solver(迭代)

    Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by th ...

  3. 【调试】DLL EXE 调试技巧

    0.随便说点 最近因为一些原因一直都没有更新博客,从今天开始要逐渐恢复了,也是对自己的鞭策. 1.本文目标 本文要说在有DLL 和 EXE源码的情况下调试DLL 和 EXE, 工具是VC++2010, ...

  4. Windows Phone 之手势识别(Flick)

    1. 引入dll (silverlight for wndows phone toolkit) 2.引入命名空间 01.xmlns:toolkit="clr-namespace:Micros ...

  5. Stack Overflow 上排名前十的与API相关的问题

    Stack Overflow是一个庞大的编程知识仓库,在Stack Overflow 上,数百万的提问被回答,并且这些回答都是高质量的.这就是为什么在Google搜索结果的排行榜上,Stack Ove ...

  6. 记2016商大ACM省赛

    比赛前三天才得到省赛的非正式参赛名额,总有点哭笑不得,笑的是是我的终究是我的,跑不掉…… 哭的是现在就剩三天了,虽然最近也一直在参加训练赛,但一直是断断续续的,对自己现在的水平并没有太大的信心…… 虽 ...

  7. 1583&colon; &lbrack;Usaco2009 Mar&rsqb;Moon Mooing 哞哞叫

    1583: [Usaco2009 Mar]Moon Mooing 哞哞叫 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 244  Solved: 126 ...

  8. Fiddler手机抓包图文教程

    上篇Fiddler教程,我们教了大家Fiddler安装配置及如何使用Fiddler进行基本的Http抓包及模拟请求,今天给大家介绍下如何使用Fiddler进行手机抓包. 运行环境为Windows 10 ...

  9. API Gateway性能比较:NGINX vs&period; ZUUL vs&period;Cloud Gateway vs&period; Linkerd&lbrack;译&rsqb;

      2018-03-04 15:07 联发科的反思 前几天拜读了 OpsGenie 公司(一家致力于 Dev & Ops 的公司)的资深工程师 Turgay elik 博士写的一篇文章(链接在 ...

  10. Confluence 6 升级自定义的站点和空间布局

    随着 Confluence 的演变.默认的站点和空间布局也会随着 Confluence 升级而让使用的所有页面进行改变.随着一些新功能的加入和一些老功能的修改,默认的布局也需要进行修改来支持这些改变. ...