1196踩方格—递推方法！
经历过一次又一次寻找递推式的失败，终于成功用递推写出来了。
很开心，手动滑稽，手动狗头
题目：
1196：踩方格
时间限制: 1000 ms内存限制: 65536 KB
提交数: 2857通过数: 1893
【题目描述】
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b、走过的格子立即塌陷无法再走第二次；
c、只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
【输入】
允许在方格上行走的步数n(n≤20)。
【输出】
计算出的方案数量。
【输入样例】
2
【输出样例】
7
【来源】
No
提交 统计信息
关于这道题所用的递推式不要着急往下翻，来跟我一起里思路。
当只能走一步的时候，有三种走法，即：左、前、右。（顺序很重要）
当走两步的时候，分类讨论：
1、第一步往左走：只能往左和往前
2、第一步往前走：可以走三个方向
3、低一步往右走：只能往右或者往前
所以共有7种走法。
我们发现：往左走的方法数和往右走的方法数是一样的，只有往前走的方法数不一样（多一种）
/*下面说的向左走：现在面临着2种选择向前走：现在面临着3种选择*/
当我们把向左走与向右走统一合并为向左走之后，变为：
当n=1时：向左走=1，向前走=1，方法数：向左走*2+向前走（刚开始要么是往左（2种），要么是往前（3种））
当n=2时，向左走=3，向前走=1，方法数：向左走*2+向前走
当n=3时（自己推，并不复杂），向左走=7，向前走=3 方法数：向左走*2+向前走
归纳：
n=n+1时，向左走=n的时候向左走*2+n的时候向前走，向前走=n的时候的向左走。
所以代码：
#include
using namespace std;
const int maxn=1e5+100;
int a[maxn];
int main()
{
int n,i,m;
cin>>n;
long ans1=1;
long ans2=1;
long a=0;
for(i=2;
i<=n;
i++)
{
a=ans2;
ans2=ans1+ans2*2;
ans1=a;
}
cout< 【1196踩方格—递推方法！】
推荐阅读
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 【迅动股票】强势股开始回调，降低仓位等待回踩
- 不甘平凡的平凡
- 使用NSAttributedString富文本踩到的坑
- 基于vue-cli2.0，webpack3升级为webpack4的踩坑之旅以及优化
- 2018-03-28|2018-03-28 搭建RocketMQ踩的坑。。。
- 踩坑记（Charles|踩坑记：Charles 打不开 HTTPS ，显示您的连接不是私密连接）
- 指数昨日回踩多方再次防守——曙光5月28日周二早评
- 推荐适合小个子的我们淘宝亲试店铺，让你少踩雷
- 踩雷了，俺有点慌