笔试题-01-有限制的跳台阶

题目描述

题目来源：字节2020.09.06笔试第一题

思想:dp

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        if(n <= 1){
            System.out.println(n);
            return;
        }

        long[][] dp = new long[n+1][2];
        dp[0][0] = 0;
        dp[1][0] = 1;
        dp[2][1] = 1;
        dp[2][0] = 1;

        for(int i = 3;i <= n;i++){
            dp[i][0] = dp[i - 1][0]+dp[i - 1][1];
            dp[i][1] = dp[i - 2][0];
        }
        System.out.println(dp[n][0]+dp[n][1]);
    }
}

• 状态定义
  • dp[i][0] 表示跳一步到达台阶
  • dp[i][1]表示跳两步到达台阶

复杂度分析

• 空间复杂度：O(N^2) dp表的空间复杂度
• 时间复杂度：O(N^2)

打赏