m个苹果放在n个盘子中有多少种结果
2024-08-31 09:03:17
题目
m个苹果放在n个盘子中有多少种结果,前置条件:
- 允许存在空盘
- 重复的摆放结果忽略不计
根据题意,也就是有3种情况,的确完全重复的摆放方式是没多大意义的
思路
这题可以用枚举的描述方式进行尾递归求解:
- 情况一:
- 存在一个空盘,甚至没有苹果或一个苹果,直接返回 1
- 情况二:
- 连盘子或苹果都没有,直接返 0
- 情况三:
- 可能有n个盘子只摆放了一个苹果,m-n的摆放占位,剩下的苹果任意摆放
- 情况四:
- 可能n个盘子为空,n-1,减去这空盘,剩下的m个苹果随意放置
- btw,存在一个以上的空盘摆放方式与图上的重复摆放方式是等价的,尾递归甚至效率并不比循环低,说了这么多,研究此类问的方法还是DP(动态规划)
将上述情况三、四二者相加就是总的所有方法(结果)
实现
package com.test.dp;
import org.junit.Test;
public class AppleOnDiskTest {
@Test
public void main(){
System.out.println(dp(5,0));
}
/**
*
* @param m apple
* @param n disk
* @return
*/
private int dp(int m,int n){
if (m <= 0 || n <= 0)
return 0;
if (m == 0 || n == 1)
return 1;
else
return dp(m-n,n) + dp(m,n-1);
}
}
模拟递归的方式求解方式
最新文章
- Binder in Java
- 【笔记】JS基础一
- Mac安装软件报“打不开。。。,因为它来自身份不明的开发者”的解决办法
- linux socket连接中 ERRNO错误
- JQuery笔记汇总
- ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket &#39;/var/lib/mysql/mysql.sock&#39; (2)--MySQL错误
- cf251.2.C (构造题的技巧)
- socket.io 入门教程
- 生成HTMLTestRunner测试报告的操作步骤——Python+selenium自动化
- Power on &; RESET 之前?
- 让.net程序自动运行在管理员权限下
- TCHAR字符串查找&;反向查找字符串
- C语言面试题分类->;回调
- Linux内存管理 (13)回收页面
- C++题解:Matrix Power Series ——矩阵套矩阵的矩阵加速
- Redis Eval Script
- Linux之Ubuntu安装搜狗输入法
- 为Docker容器设置http代理
- Linux下计划任务以及crontab权限问题
- Web Automation with Selenium (C#)
热门文章
- docker官方文档翻译5
- 菜鸟笔记 -- Chapter 6.2.1 权限修饰符
- WKWebView简单使用及关于缓存的问题
- WebGL学习笔记(4)
- 在cmd下面执行.py文件时提示ModuleNotFoundError 但是 IDE 不报错
- poj 2763 Housewife Wind : 树链剖分维护边 O(nlogn)建树 O((logn)&#178;)修改与查询
- EF core Code First 简单的使用方法
- php mysql 计算经纬之间距离 范围内筛选
- Yaf学习(一)----Linux安装Yaf
- JZOJ 5943. 树