#3887. 奶牛散步(C++四级)

奶牛散步(C++四级)

题目描述

🚀️

总时间限制: 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.