目录

牛客_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 cint 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);}}
}