剑指offer（07-09）题解

07题解–斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数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);
    }
    }
}

08题解–跳台阶

题目描述

一只青蛙一次可以跳上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);
    }
    }
}

09题解–变态跳台阶

题目描述

一只青蛙一次可以跳上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;
        }
    }
}