算法学习——递推之猴子爬山
2023-02-18 16:40:26 时间
算法描述
一个猴子沿着一座山的n级台阶向上爬,猴子上山一步可跳1级或3级,试求上山的n级台阶有多少种不同的爬法
算法思路
利用递推的思想,猴子在第n级台阶上,它之前可能在第n-1级台阶上或者是在n-3级台阶上,由此可得到递推的公式
f(n)代表着n级台阶共有的爬法
f(1) = 1
f(2)= 1
f(3) =2 三步,每一步都是跳1级台阶
走了一步,一步跳3级
f(n)=f(n-1)+f(n-3) (n>3)
算法实现
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.close();
long[] k = new long[10000];
k[1]=1;
k[2]=1;
k[3]=2;
for(int i=4;i<=n;i++){
k[i]=k[i-1]+k[i-3];
}
System.out.println(k[n]);
结果
相关文章
- iterm2 快捷键(转载)
- Too many authentication failures for xxxx_username
- peewee insert 数据时报错:'buffer' object has no attribute 'translate'
- virtualenv 虚拟环境报错:setuptools pip wheel failed with error code 1
- supervisor 安装、配置、常用命令
- _ssl.c:510: error:14077410:SSL routines:SSL23_GET_SERVER_HELLO:sslv3 alert handshake failure
- [MySQL]支持 emoji(字符集问题)
- [MySQL]长连接和短链接(转载)
- 解决 InsecurePlatformWarning: A true SSLContext object is not available.
- Mac总是自动启动脚本
- Max retries exceeded with url
- brew tap homebrew-science fails
- 持续集成是什么?(转载)
- [编辑器]vim常用操作
- Mac下中文输入法突然没了选字框
- install dm.xmlsec.binding 失败
- [MySQL]创建数据库以及设置编码
- [MySQL]备份和导入
- [MySQL]删除一张表的所有数据
- [MySQL]增加约束键