概述
Problem P ID：1016
简单题意：在一个无限大的平面，只能向前、向左、向右走，不能向后走，走过的路不能再走。给出走的步数n（n<=20)，求总方案数。
解题思路形成过程：设F(n)为走n步的总方案数，a(n)为走n步最后一步为向前走的总数，b(n)为走n步最后一步为向左走或向右走的总数。
可以推出：①F(n)=a(n)+b(n); （比较显而易见）
②a(n)=a(n-1)+b(n-1); （第n-1步不管是向前走的还是向左或向右走的都可以在第n步向前走）
③b(n)=2*a(n-1)+b(n-1); （第n-1步如果是向前走的，那么在第n步既可以向左走，也可以向右走，所以a(n-1)要乘以2；而第n-1步如果是向左走的，则不能向右走，第n-1步向右走的不能向左走，否则道路会塌陷，因此b(n-1)不用乘以2）
④a(n-1)=F(n-2); （不管第n-2步是如何走的，都可以在第n-1步向前走）
由上述4式可得状态转移方程式：a[i]=2*a[i-1]+a[i-2];
又因：a[0]=3; a[1]=7; 问题便迎刃而解了。
感想：又是一个自己想了很久，画了很久没有解决的问题，还是从网上找的相关算法。不过看了别人的算法很快就理解了，不像上个题还要自己再思考好一会儿。
这个题也同样让我感概万千，会做了以后觉得很简单，但是自己独自面对这种问题时很多应该有的想法并不会萌生，DP啊DP，还是各种递推，各种拆分，各种从后一步往前一步找答案。经验、能力还不足，还需努力，努力刷题。
代码：#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[21];
void dp()
{
a[0]=3;
a[1]=7;
for(int i=2;i<=19;++i){
a[i]=2*a[i-1]+a[i-2];
}
}
int main()
{
int n;
scanf("%d",&n);
dp();
while(n--)
{
int m;
scanf("%d",&m);
printf("%dn",a[m-1]);
}
return 0;
}
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[21];
void dp()
{
a[0]=3;
a[1]=7;
for(int i=2;i<=19;++i){
a[i]=2*a[i-1]+a[i-2];
}
}
int main()
{
int n;
scanf("%d",&n);
dp();
while(n--)
{
int m;
scanf("%d",&m);
printf("%dn",a[m-1]);
}
return 0;
}
最后
以上就是单纯饼干为你收集整理的DP 动态规划 Problem P 1016 不向后走的走路方案数的全部内容，希望文章能够帮你解决DP 动态规划 Problem P 1016 不向后走的走路方案数所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复