每日OJ题_牛客_DP2跳台阶_动态规划_C++_Java

目录

牛客_DP2跳台阶_动态规划

题目解析

C++代码

Java代码

牛客_DP2跳台阶_动态规划

跳台阶_牛客题霸_牛客网

题目解析

        当前值只和数组的前两个值有关，在往前面的就无关了，所以没必要申请一个数组，直接使用两个变量即可，这样空间复杂度就满足要求了。

C++代码

#include <iostream>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    if(n < 3)
    {
        cout << n << endl;
        return 0;
    }
    int a = 1; // 第一个台阶跳法
    int b = 2; // 第二个台阶跳法
    for(int i = 3; i <= n; ++i)
    {
        // a b c
        int c = a + b;
        if(i == n)
        {
            cout << c << endl;
            break;
        }
        a = b;
        b = c;
    }
    return 0;
}

Java代码

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a = 1, b = 1, c = 0;
        for(int i = 2; i <= n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        if(n == 0 || n == 1)
        {
            System.out.println(n);
        }
        else
        {
            System.out.println(c);
        }
    }
}