题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。 n<=39
思路解析
其实今天解析的三道题目刚好都属于算法题目里的同一分支,就是递归,也可以说是动态规划,就是要找出状态转换方程,这样我们才能进行解答。斐波那契数列属于最简单的动态规划,条件基本就已经给出来了就是,后一项是前两项的和,所以状态转换方程也就出来了dp[i]=dp[i-1]+dp[i-2] (i>=2)这里下标是以数组的下标来进行的。
源代码
public class Solution {
public int Fibonacci(int n) {
if(n==0)
return 0;
else if (n==1) {
return 1;
}
else {
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
}
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
思路解析
这就是斐波那契数列的一个变形,虽然没有直接告诉你,但是我们可以简单分析一下,假如我们跳N阶台阶是不是就是意味着是我们在跳了N-1阶台阶的基础上再跳一阶,按照这个思路,是不是也能理解为也是在已经跳了N-2阶台阶的基础上再跳2阶,所以显然跳N阶台阶的方案就已经出来了,就是跳N-1阶与N-2阶方案之和,显然也就变成了一个斐波那契数列的问题,状态方程还是上一题的方程
源代码
public class Solution {
public int JumpFloor(int target) {
if(target==1)
return 1;
else if(target==2)
return 2;
else {
return JumpFloor(target-1)+JumpFloor(target-2);
}
}
}
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路解析 这一题与上述的那一题大同小异,只要注意一些小问题,显然该题的状态转换方程也和上题差不多,但是这题,有一个不同的地方就是,他不仅可以跳一步,两步,他还能跳三步,甚至是N步,所以,显然N阶的方案里面肯定也包括了在跳N-3阶的基础上再跳3阶的方案。一次类推,所以显然 dp[i]=dp[i-1]+dp[i-2]+…+dp[1],你以为这样就结束了吗?NONONO,不要忘记了,他还能跳N阶,所以状态方程应该是dp[i]=dp[i-1]+dp[i-2]+…+dp[0]+1。 源代码
public class Solution {
public int JumpFloorII(int target) {
if(target==1)
return 1;
else
{
int sum=0;
for(int i=1;i<target;i++)
{
sum+=JumpFloorII(i);
}
return sum+1;
}
}
}
都看到这里了,如果觉得对你有帮助的话,可以关注博主的公众号,新人up需要你的支持。