動态規劃基礎題(第1題):被變換的菲波那切數列

碎碎念

• 最近開始學習動态規劃，相比之前學習的算法，諸如：枚舉、貪心、全搜尋等算法要複雜不少，這個山頭不好攻。
• “自己選的路，跪着也要走下去”，這話不是我說的，是老碼農對我說的，上了賊船下船難啊。

标簽

• 動态規劃、菲波那切數列

合集

• 【動态規劃】基本DP
• 【數學】

題目位址

C - Typical Stairs

• https://atcoder.jp/contests/abc129/tasks/abc129_c

問題描述

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step. He can climb up one or two steps at a time.

However, the treads of the a 1 _1 1​-th, a 2 _2 2​-th, a 3 _3 3​-th, … \ldots ……, a M _M M​-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps? Find the count modulo 1 000 000 007.

Constraints

• 1≤N≤105
• 0≤M≤N−1
• 1 ≤ \leq ≤ a 1 _1 1​ < a 2 _2 2​ … < a M _M M​ ≤ \leq ≤ N-1

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

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]);
}