首页 > 代码库 > 【noi 2.6_4982】踩方格(DP)
【noi 2.6_4982】踩方格(DP)
题意:一个无限大的方格矩阵,能向北、东、西三个方向走。问走N步共有多少种不同的方案。
解法: f[i]表示走 i 格的方案数。
状态转移方程推导如下——
设l[i],r[i],u[i]分别为第 i 步向西、东、北的方案数,f[i]为总方案数。
l[i]=l[i-1]+u[i-1], r[i]=r[i-1]+u[i-1], u[i]=l[i-1]+r[i-1]+u[i-1]
f[i]=l[i]+r[i]+u[i]
=2*l[i-1]+2*r[i-1]+3*u[i-1]
=2*f[i-1]+u[i-1]
=2*f[i-1]+f[i-2]
于是代码就非常简单了:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 int f[25]; 8 9 int main()10 {11 int n;12 scanf("%d",&n);13 f[1]=3, f[2]=7;14 for (int i=3;i<=n;i++)15 f[i]=2*f[i-1]+f[i-2];16 printf("%d\n",f[n]);17 return 0;18 }
【noi 2.6_4982】踩方格(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。