DP 1016

简单题意：在一无限大的二维平面中，我们做如下假设：
1、  每次只能移动一格；
2、  不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、  走过的格子立即塌陷无法再走第二次；

求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。

解题思路：设第n次左右走为Q[n]，第n次向上走位Z[n]，则f(n) = Q[n] + Z[n],因为左右走只能向左或者向右走，而向上走可以向左上或者右上走，所以Z[n] = Q[n - 1] + Z[n - 1]

Q[n] = 2 * Z[n - 1] + Q[n - 1] 所以 f[n] = 2 * f[n-1] + f[n - 2]

AC代码：

#include
using namespace std;
int main()
{int n;long long int a[30];cin >> n;a[1] = 3;a[2] = 7;for(int i = 3 ; i <= 20;i ++)a[i] = 2 * a[i - 1] + a[i - 2];while(cin >> n){cout << a[n] << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！