# 🌱 Lời giải Mely Educational Contest 04 bài D : Leo cầu thang.

>[color=pink] Nếu bạn cảm thấy Edit này chất lượng tiếc gì một upvote và giới thiệu team với mọi người nhé :heart:

###### 📋 Content:
[TOC]
____
## Nhận xét :label:
:question: Đây là bài quy hoạch động cơ bản với công thức chuyển trạng thái như sau :
>[color=green]
>- Gọi $dp_i$ là số cách leo được lên bậc thang thứ ***i***
>- Nếu bậc thứ ***i*** bị hỏng thì $dp_i$ ***= 0***
>- Ngược lại $dp_i$ = ($dp_{i-1}$ + $dp_{i-2}$) % $(10^9+7)$ (do bậc thang thứ ***i*** có thể leo lên được từ bậc thang thứ ***i-1*** hoặc ***i-2***), **lưu ý nhỏ** : trường hợp i = 1.

## Code mẫu :bulb:
> **Time:** $O(n)$
> **Space:** $O(n)$
> **Algo:** Dynamic programing.
> [color=lightgreen]
:::success
:::spoiler code mẫu

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
const int maxN = 2e5 + 5;
const int N = 2e6;
const int mod = 1e9 + 7;

int n,m;
int dp[maxN];
int invalid[maxN];

void Solve()
{
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        int x;
        cin >> x;
        invalid[x] = 1;
    }
    dp[0] = 1;
    for(int i = 1;i <= n;i++)
    {
        if(invalid[i]) continue;
        dp[i] = (dp[i] + dp[i-1]) % mod;
        if(i >= 2) dp[i] = (dp[i] + dp[i-2]) % mod;
    }
    cout << dp[n];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //Prepare();
    int tt;
    //cin >> tt;
    tt = 1;
    while(tt--)
    {
        Solve();
    }
}

:::success