欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer:跳台阶/变态跳台阶(动态规划解法)

程序员文章站 2022-04-02 21:20:52
...

这两题从动态规划的角度思考,按照动态规划的解题框架进行分析,非常的简单和清晰。

跳台阶

1. 题意

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

2. 分析

2.1 确定状态

2.1.1 最后一步

  • 先不管前面是是如何跳跃的,最后一定会跳跃到台阶n
  • 根据题目的描述,青蛙只可能从台阶n-1或者台阶n-2跳跃到台阶n
  • 那么如果我知道了有多少种跳法能跳到台阶n-1台阶n-2,那么跳到台阶n的跳法自然也就出来了,就是二者之和

2.1.2 子问题

  • 原问题是求,有多少种跳法跳到台阶n
  • 现在要解决这个原问题,只需要知道有多少种跳法跳到台阶n-1台阶n-2
  • 问题不变,但问题规模变小了,那么状态也就定义出来了
  • f[i]表示有几种跳法能够跳到台阶i,最后返回f[n]即是答案

2.2 状态转移方程

f[i]=f[i1]+f[i2]i>1f[i] = f[i-1] + f[i-2](i > 1)

2.3 初始值和边界条件

  • f[0]=1,0f[0] = 1,跳到台阶0只有一种跳法,那就是不跳
  • f[1]=1,11f[1] = 1,跳到台阶1,也只有一种跳法,那就是跳1级

2.4 计算顺序

  • f[0,1,2,........n]f[0,1,2,........n]
  • 时间复杂度:O(n)
  • 空间复杂度:O(n),因为只需要开一个长度为n+1的数组

3. 代码

  public int JumpFloor(int target) {

        int[] f = new int[target + 1];
        f[0] = 1;
        f[1] = 1;

        for (int i = 2; i <= target ; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f[target];
    }

变态跳台阶

1. 题意

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

2.分析

2.1 确定状态

2.1.1 最后一步

  • 与上题完全一样,不管前面怎么跳,最后一定能跳到台阶n
  • 根据题意,一只青蛙可以跳上1级、2级…n级台阶
  • 那么最后一步跳到台阶n的就可能是台阶n-1,台阶n-2...............台阶0
  • 那么我只需要知道跳到台阶n-1、台阶n-2、.......、台阶0各有多少种跳法,跳到台阶n的跳法也就是他们之和

2.1.2 子问题

  • 原问题是求,有多少种跳法跳到台阶n
  • 现在要解决这个原问题,只需要知道有多少种跳法跳到台阶n-1、台阶n-2、.......台阶0
  • 问题不变,但问题规模变小了,那么状态也就定义出来了
  • f[i]表示有几种跳法能够跳到台阶i,最后返回f[n]即是答案

2.2 转移方程

f[i]=f[i1]+f[i2]+....+f[0]f[i] = f[i-1] + f[i-2] + .... + f[0]

2.3 边界条件和初始值

  • f[0]=1,0f[0] = 1,跳到台阶0只有一种跳法,那就是不跳
  • f[1]=1,11f[1] = 1,跳到台阶1,也只有一种跳法,那就是跳1级

2.4 计算顺序

  • 同上
  • 时间复杂度

3. 代码

public int JumpFloorII(int target) {
        int[] f = new int[target +1];
        //0层不跳也是一种跳法
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= target ; i++) {
            for (int j = i -1;j >= 0; j-- ){
                f[i] += f[j];
            }
        }
        return f[target];
    }


相关标签: 算法刷题笔记