【题目描述】 有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设: a、每走一步时,只能从当前方格移动一格,走到某个相邻的方格上; b、走过的格子立即塌陷无法再走第二次; c、只能向北、东、西三个方向走; 请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。 【输入】 允许在方格上行走的步数n(n≤20)。 【输出】 计算出的方案数量。 【输入样例】 2 【输出样例】 7
#include <bits/stdc++.h> using namespace std; int long long up[25],l[25],r[25]; int main() { int n,i; cin>>n; up[0]=1; for(i=1;i<=n;i++) { up[i]=up[i-1]+r[i-1]+l[i-1]; //向上:第i-1步不可能向下走,所以第i步往上、左、右都行,所以i-1有多少种走法,i就有多少种走法; l[i]=up[i-1]+l[i-1]; //向左:若第i步是向左,则第i-1步不能向右,只能向左或向上
r[i]=up[i-1]+l[i-1]; //同上
//这三行代码都是这几种情况相加得到的,所以就是方法的数目
} cout<<up[n]+l[n]+r[n]<<endl; //把他们加起来就是答案 return 0; }
第i步有三种走法,向上,向左,向右
原文链接: https://www.cnblogs.com/liufei-/p/10105508.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/286757
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!