题目描述：从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？ 输入样例：3 输出样例：17 前一步分配的点都可以向左或是向右加上向上，即2种选择，而前两步分配的点都可以向上走，而每个向上走的点都可以在前一步再多出一种选择（向左或向右），所以算法为F(n)=F(n-1)*2+F(n-2)
#include <iostream> #include <string> #include <stdio.h> using namespace std; int main() { int n; cin>>n; int *a=new int[n+1]; a[1]=3; a[2]=7; for(int i=3;i<=n;i++) { a[i]=a[i-1]*2+a[i-2]; } cout <<a[n]; delete [] a; return 0; }