题目描述

🚀️

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB

描述

从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点 共有多少种走法？

输入

一个数字，代表N,N<=1000

输出

输出有多少方案

样例输入

2

样例输出

7

思路

f[i][0]表示走i步第一步向右走，f[i][1]表示向上，f[i][2]表示向左. 所以，以f[i][0]为例，因为第一步向右走，就相当于以原地右边一步为起点，“第一步”只能向右或向上走i-1步，所以f[i][0]=f[i-1][0]+f[i-1][1]; 注意，如果第一步向上，三个方向都可以走

代码 只要把思路转换成代码就行啦 😃你学废了吗 😄

Limitation

1s, 1024KiB for each test case.