【noi 2.6_4982】踩方格(DP)
2024-09-02 07:50:57
题意:一个无限大的方格矩阵,能向北、东、西三个方向走。问走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 }
最新文章
- java中的访问修饰符
- Python开发程序:选课系统-改良版
- HTML5离线缓存问题
- 在android 6.0(API 23)中,Google已经移除了移除了Apache HttpClient相关的类
- 使用XtraReport的CalculatedFiled(计算字段)实现RDLC报表中表达式
- Spring Boot的快速启动和部署
- paip.提升效率---filter map reduce 的java 函数式编程实现
- Android --- 斗地主 [牌桌实现源码]
- Win10环境下的Scrapy结合Tor进行匿名爬取
- 一个包含所有c++的头文件的头文件
- linux C++通过ntp协议获取网络时间
- no suitable driver found for jdbc:mysql//localhost:3306/..
- Beta冲刺 第六天
- Fiddler对Android应用进行抓包
- .Net Core 实践 - 使用log4net记录日志(3)— log4net向ElasticSearch写日志
- function call操作符(operator()) 仿函数(functor)
- kali 解决Metasploit拿到shell后显示中文乱码问题
- Java多线程学习(吐血超详细总结)(转)
- 计算概论(A)/基础编程练习1(8题)/2:苹果和虫子
- day 28 hasattr getattr serattr delattr 和带__内置__ 类的内置方法
热门文章
- TCP/IP五层模型-应用层-DNS协议
- 3.利用jmeter制作性能脚本
- 【Linux】Linux基础命令 - 目录相关的命令 ls 、cd、du
- Xctf攻防世界—crypto—Normal_RSA
- Java入门者:如何写出美观的Java代码?
- mybatis中传集合时 报异常 invalid comparison: java.util.Arrays$ArrayList and java.lang.String
- 微信小程序腾讯地图SDK使用方法
- uni-app 开发随笔(踩坑记录)
- python_mmdt:从0到1--实现简单恶意代码分类器(二)
- mybatis源码解析之架构理解