动态规划基础题(第1题): 被变换的菲波那切数列
动态规划基础题(第1题): 被变换的菲波那切数列
小码匠
发布于 2022-06-16 18:04:09
发布于 2022-06-16 18:04:09
代码可运行
运行总次数：0
代码可运行
碎碎念
- 最近开始学习动态规划，相比之前学习的算法，诸如：枚举、贪心、全搜索等算法要复杂不少，这个山头不好攻。
- “自己选的路，跪着也要走下去”，这话不是我说的，是老码农对我说的，上了贼船下船难啊。
标签
- 动态规划、菲波那切数列
合集
- 【动态规划】基本DP
- 【数学】
题目地址
C - Typical Stairs
- https://atcoder.jp/contests/abc129/tasks/abc129_c
问题描述
Input
Input is given from Standard Input in the following format:
N M
a1
a2
.
.
.
aM
Output
Print the number of ways to climb up the stairs under the condition, modulo 1 000 000 007.
Sample Input 1
6 1
3
Sample Output 1
4
There are four ways to climb up the stairs, as follows:
- 0→1→2→4→5→6
- 0→1→2→4→6
- 0→2→4→5→6
- 0→2→4→6
Sample Input 2
10 2
4
5
Sample Output 2
0
There may be no way to climb up the stairs without setting foot on the broken steps.
Sample Input 3
100 5
1
23
45
67
89
Sample Output 3
608200469
Be sure to print the count modulo 1 000 000 007.
思路
- 基于菲波那切数列改编的题目
- 基于动态规划思路可以解题
题解
小码匠题解1
- 这个题解：共有36个测试点，只有3个测试点没过，悲剧，暂时我还不知道哪里错了。
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
const long long mod = 1000000007;
int n, m;
cin >> n >> m;
vector<int> vi(m);
vector<long long> dp(n + 1);
long long ans = 0;
dp[0] = 1;
dp[1] = 1;
for (int i = 0; i < m; i++) {
cin >> vi[i];
if (vi[i] == 1) {
dp[1] = 0;
ans++;
}
}
for (int i = 2; i <= n; i++) {
if (i == vi[ans]) {
dp[i] = 0;
ans++;
} else {
dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
}
}
cout << dp[n];
}
小码匠题解2
- 这个是看了题解后又修改后的代码，AC了
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
const long long mod = 1000000007;
int n, m, temp;
cin >> n >> m;
vector<bool> vb(n, false);
vector<long long> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 0; i < m; i++) {
cin >> temp;
vb[temp - 1] = true;
if(temp == 1) {
dp[1] = 0;
}
}
for (int i = 2; i <= n; i++) {
if (!vb[i - 1]) {
dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
}
}
cout << dp[n];
}
参考题解
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, mod = 1e9 + 7;
int n, m, a[N], f[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= m; i++) {
scanf("%d", &x), a[x] = 1;
}
f[0] = 1;
for (int i = 1; i <= n; i++) {
if (!a[i]) {
f[i] = (f[i - 1] + f[i - 2]) % mod;
}
}
printf("%d\n", f[n]);
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-05-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
