# 🌱 Lời giải Mely Educational Contest 04 bài F :Tí và Tèo.

>[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:
+ Ta gọi $dp[i][v]$ là số cách để tạo ra mảng đến vị trí thứ $i$ và giá trị của $X_i = v$.
+ Ta đặt một trường hợp ảo tại ví trí $0$, nhận xét tại vị trí $0$ giá trị $X_0$ có thể thay thế bằng bất kỳ giá trị nào **(tức là $dp[0][v] = 1$ với mọi $v$)**
+ Bây giờ với tất cả vị trí $i>0$. Nếu $x_i = 0$, chúng ta có thể thay thế nó bằng bất kỳ giá trị nào. Tuy nhiên, nếu chúng ta thay thế nó bằng $v$ thì giá trị trước đó phải là $v-1$, $v$ hoặc $v+1$. Do đó, số cách để tạo ra mảng đến vị trí $i$, là tổng của số lượng mảng tạo ra đến vị trí $i-1$ có giá trị kết thúc trước đó là $v-1$, $v$ và $v+1$. Nếu $x_i = v$ từ đầu vào thì chỉ cho phép $dp[i][v]$ **(tức là $dp[i][j] = 0$ nếu $j ≠v$)**. Nếu không thì vẫn là $dp[i][v] = dp[i-1][v-1] + dp[i-1][v] + dp[i-1][v+1]$.
## Code mẫu :bulb:
> **Time:** $O(n.m)$
> **Space:** $O(n.m)$
> **Algo:** Dynamic programing.
> [color=lightgreen]
:::success
:::spoiler code của LeThanhMinh

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n, m;
  cin >> n >> m;
  vector<vector<int>> dp(n,vector<int>(m+1,0));
  int x0;
  cin >> x0;
  if (x0 == 0) {
    fill(dp[0].begin(), dp[0].end(), 1);
  } else {
    dp[0][x0] = 1;
  }
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    if (x == 0) {
      for (int j = 1; j <= m; j++) {
	for (int k : {j-1,j,j+1}) {
	  if (k >= 1 && k <= m) {
	    (dp[i][j] += dp[i-1][k]) %= mod;
	  }
	}
      }
    } else {
      for (int k : {x-1,x,x+1}) {
	if (k >= 1 && k <= m) {
	  (dp[i][x] += dp[i-1][k]) %= mod;
	}
      }
    }
  }
  int ans = 0;
  for (int j = 1; j <= m; j++) {
    (ans += dp[n-1][j]) %= mod;
  }
  cout << ans << endl;
}

:::success