关键词:
- 斐波那契数列 - 矩阵算法(O(lgn)) - 待补充
- 跳台阶 - 经典问题
- 递归 - basic解法,浪费栈空间
- 动态规划 - 常规解法,转移方程可以有很多变化
- 打表 - 按照转移方程提前计算
- 注意:台阶数很多的时候,需要手写大数加法
- 变态跳台阶/观察法
- 跳石板/动态规划
- 爬楼梯/大数跳台阶
- 爬楼梯2/大数加法
变态跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法 (2^n-1)
思路
- 思路1
- 青蛙一次可以跳1~n之间的台阶数,考虑如下情况
- 青蛙一次跳n阶,则1~n-1的所有台阶均不经过
- 青蛙第一次跳n-1阶,第二次跳1阶,等价于仅选中n-1阶
- 所以,观察可得,每种跳台阶方案都对应了1~n-1中的唯一一组选择
- 1~n-1共n-1级台阶,每级台阶都有选or不选两种情况
- 总的跳法数目为(2^n-1)
- 青蛙一次可以跳1~n之间的台阶数,考虑如下情况
- 思路2
- (f(n-1)=2^n-2) 数学归纳法
- (f(n)=1+f(n-1)+f(n-2)+f(n-3)+...+f(2)+f(1))
- (f(n)=2^n-1)
跳石板
小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3.......
这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,小易单次只能往前跳K的一个约数(不含1和K)步,即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板,他想跳到编号恰好为M的石板去,小易想知道最少需要跳跃几次可以到达。
例如:
N = 4,M = 24:
4->6->8->12->18->24
于是小易最少需要跳跃5次,就可以从4号石板跳到24号石板
思路
状态转移
(steps[i+j]=min(steps[i]+1,steps[i+j]))
(steps[i+i/j]=min(steps[i]+1,steps[i+i/j]))
注意这里对约数的处理很巧妙,j from 2 to i^(1/2)
代码
#include<iostream>
#include<climits> //INT_MAX,INT_MIN等
#include<cmath> //min,max等函数
#include<vector>
using namespace std;
int main()
int N,M;
while(cin>>N>>M)
vector<int> steps(M+1,INT_MAX);
steps[N]=0;
for(int i=N;i<=M;i++)
if(steps[i]==INT_MAX)
continue;
//快速计算i的约数
for(int j=2;(j*j)<=i;j++)
if(i%j==0)
if(i+j<=M)
steps[i+j]=min(steps[i]+1,steps[i+j]);
if(i+i/j<=M)
steps[i+i/j]=min(steps[i]+1,steps[i+i/j]);
if(steps[M]==INT_MAX)
steps[M]=-1;
cout<<steps[M]<<endl;
爬楼梯
题目描述
在你面前有一个n阶的楼梯,你一步只能上1阶或2阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯。
输入描述:
一个正整数n(n<=100),表示这个楼梯一共有多少阶
输出描述:
一个正整数,表示有多少种不同的方式爬完这个楼梯
思路
不愧是校招题目,大坑在数据范围,unsigned long long不够用,需要手写大数加法
代码
#include<iostream>
using namespace std;
int main()
int n;
cin>>n;
int num[103][30]=0;//二维数组的初始化,int数组进行大数加法
num[1][29]=1;
num[2][29]=2;
for(int i=3;i<=100;i++)
//从低位向高位计算
int carry=0;//进位初始设置为0
for(int j=29;j>=0;j--)
num[i][j]=(num[i-1][j]+num[i-2][j]+carry)%10;
carry=(num[i-1][j]+num[i-2][j]+carry)/10;
int j=0;
while(num[n][j]==0)
j++;
for(int i=j;i<30;i++)
cout<<num[n][i];
cout<<endl;
爬楼梯2
题目描述
在你面前有一个n阶的楼梯(n>=100且n<500),你一步只能上1阶或3阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯(到最后一层为爬完)。
输入描述:
一个正整数,表示这个楼梯一共有多少阶
输出描述:
一个正整数,表示有多少种不同的方式爬完这个楼梯
代码
#include<iostream>
using namespace std;
int len=99;
int num[501][100];//这里大数的位数会很高,用len+1表示
int main()
num[1][len]=1;
num[2][len]=1;
num[3][len]=2;
for(int i=4;i<500;i++)
int carry=0;
for(int j=len;j>=0;j--)
num[i][j]=(num[i-1][j]+num[i-3][j]+carry)%10;
carry=(num[i-1][j]+num[i-3][j]+carry)/10;
int n;
cin>>n;
int j=0;
while(num[n][j]==0)
j++;
for(;j<=len;j++)
cout<<num[n][j];
cout<<endl;
最强解析面试题:跳台阶&超级跳台阶「建议收藏!」(代码片段)
文章目录最强解析面试题:跳台阶&超级跳台阶「建议收藏!」1、题目-跳台阶示例1思路代码2、题目-超级跳台阶思路代码Q&A附录最强解析面试题:跳台阶&超级跳台阶「建议收藏!」文章讲解“跳台阶&... 查看详情
最强解析面试题:跳台阶&超级跳台阶「建议收藏!」(代码片段)
文章目录最强解析面试题:跳台阶&超级跳台阶「建议收藏!」1、题目-跳台阶示例1思路代码2、题目-超级跳台阶思路代码Q&A附录最强解析面试题:跳台阶&超级跳台阶「建议收藏!」文章讲解“跳台阶&... 查看详情
剑指offer跳台阶(代码片段)
题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。解题代码:functionjumpFloor(number)//writecodehere//跳台阶问题是斐波那契数列的一个形式转换... 查看详情
跳台阶问题(代码片段)
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级,求总共有多少种跳法。问题分析: 1f(n)=f(n-1)=1n=12f(n)=1+1=2n=2当第一次跳一个台阶时,有一种方法,当第一次跳两个台阶时有一种方法3f(n)=2+1=3n=3当第一次跳一个台阶时有f(3-... 查看详情
▷青蛙跳台阶◁(代码片段)
青蛙跳台阶题目一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)找规律代码实现classSolution:defJumpFloor(self,n):ifn==0:return0;ifn==1:re... 查看详情
变态跳台阶(代码片段)
题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法思路:数学题,找规律即可intjumpFloorII(intn)intn1=1;while(n>1)n1=n1*2;n--;returnn1; 查看详情
跳台阶(代码片段)
题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。#-*-coding:utf-8-*-classSolution:defjumpFloor(self,number):ifnumber<=2:returnnumbera,b=1,2whilenumber>2:number-... 查看详情
变态跳台阶(代码片段)
题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路:用数学归纳法,容易证明f(n)=2**(n-1)pythonsolution:#-*-coding:utf-8-*-classSolution:defjumpFloorII(self,nu... 查看详情
跳台阶问题(递归动态规则变态跳台阶)(代码片段)
题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 分析:青蛙每次只有一阶或者两阶两种跳法,那么:假设第一次跳的是一阶,那么剩下的n-1个台阶,跳法是f(n-1)假设第... 查看详情
跳台阶,变态跳台阶,矩阵覆盖(代码片段)
一、跳台阶1、问题描述跳台阶:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。2、代码classSolution:defjumpFloor(self,number):#writecodeherea=1b=1foriinrange(number... 查看详情
剑指offer跳台阶(代码片段)
题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 题目链接:跳台阶 思路:类似于斐波那契序列,跳上第n(n>3)级台阶,之前最后一步跳1级或2级。 ... 查看详情
剑指offer变态跳台阶(代码片段)
...现代码解法3实现代码题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解法1本题是【剑指Offer】跳台阶的进化版本。原来的青蛙只可以跳上1级或2级... 查看详情
跳台阶问题(代码片段)
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 代码格式要求:publicclassSolutionpublicintJumpFloor(inttarget) 解题思路:这是一道动态规划的问题... 查看详情
剑指:跳台阶(代码片段)
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 分析:因为只能跳1级或2,假设n阶有f(n)种跳法。所以有两种情况:a、如果第一次跳的是1阶,... 查看详情
青蛙跳台阶问题(代码片段)
问题一:有一只青蛙,需要跳上100级台阶。青蛙每次可以调一级或者两级台阶。问青蛙有多少种方式可以跳100级台阶。思路:逆推 当青蛙站在100级台阶上时,那它跳上100级时有可能是从99级跳一级上来的,... 查看详情
跳台阶(代码片段)
题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路:推导找规律,类似斐波那契,用递归或循环实现intjumpFloor(intn) intn1=1; intn2=2; intn3=0; if(n==1)returnn1; i... 查看详情
剑指offer[9]——变态跳台阶(代码片段)
题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。这个题目是跳台阶的进阶版,其实跟大家分析一下,这道题其实比上一道题简单。在这道题目中,... 查看详情
剑指offer08跳台阶(代码片段)
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。java版本:publicclassSolutionpublicstaticvoidmain(String[]args)longstartTime=System.currentTimeMillis();System.out.println("... 查看详情