题解 | 跳台阶扩展问题
跳台阶扩展问题
https://www.nowcoder.com/practice/953b74ca5c4d44bb91f39ac4ddea0fee
解题思路
这是一道动态规划的题目，我们可以这样分析：
- 当青蛙处在第
级台阶时，它可以从前面的任意一级台阶跳过来
- 因此
- 同理
- 两式相减得：
- 最终可以推导出
代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
cout << (1 << (n-1)) << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(1 << (n-1));
sc.close();
}
}
n = int(input())
print(1 << (n-1))
算法及复杂度
- 算法：数学推导/动态规划
- 时间复杂度：
- 空间复杂度：
美团工作强度 1650人发布
投递美团等公司9个岗位 >
难怪小公司那么挑剔，让你们这些大佬把位置拿了