3
7
思路: 我自己还是没找出来, 画画图然后参考了其他大佬的博客
大佬解析 1(感觉这个最好理解): 因为 n+1 时都可以往两个方向或者三个方向; 三个方向是为 n 时向上的状态; 为 n 时有多少个向上的状态? 当 n-1 有多少状态, n 就有多少个向上的状态; 所以递推公式为 a[n]=2*a[n-1]+a[n-2];
大佬解析 2: 赤裸裸的递推问题, 设第 n 步的走法为 F(n), 往上走的步数为 a(n), 往左或往右走的步数为 b(n);
所以 F(n)=a(n)+b(n); 接下来分别找前一个状态. 因为不能往下走, 所以向上走的步数只有一种选择就是上一次的步数相加: a(n)=a(n-1)+b(n-1)(前 (n-1) 步内往上走的步数 + 前 (n-1) 步内往左或右的步数); 又因为走过的不能返回, 所以往左或右走只有一种方法, 但向上走可以是左上和右上两种, 因此 b(n)=2*a(n-1)+b(n-1); 化简得 F(n)=2*F(n-1)+F(n-2);
- #include <stdio.h>
- #include <iostream>
- #include <cstring>
- using namespace std;
- int f(int x)
- {
- if(x==0)
- {
- return 1;
- }
- if(x==1)
- {
- return 3;
- }
- return 2*f(x-1)+f(x-2);
- }
- int main()
- {
- int n;
- cin>> n;
- while(n--)
- {
- int m;
- cin>> m;
- cout << f(m) <<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3719229.html