cppProgram/ArrayDescription.cpp at main · Tirthankarpal/cppProgram · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "bits/stdc++.h"
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll> > dp;
ll m;
ll dynamic(ll i,ll prev,vector<ll> &arr) {
    if(i>=arr.size()){
        return dp[i][prev]=1;
    }
    if(dp[i][prev]!=-1){
        return dp[i][prev];
    }
    if(arr[i] != 0 &&prev!=0 && abs(arr[i]-prev)>1){
        return dp[i][prev]=0;
    }
    if(arr[i]==0){
        ll total=0;
        if (prev==0){
            for(int j=1;j<=m;j++){
                total=(total+dynamic(i+1,j,arr))%1000000007;
            }
        }
        else{
            if(prev+1<=m){
                total=(total+dynamic(i+1,prev+1,arr))%1000000007;
            }
            if(prev-1>0){
                total=(total+dynamic(i+1,prev-1,arr))%1000000007;
            }
            total=(total+dynamic(i+1,prev,arr))%1000000007;
        }
        return dp[i][prev]=total;
    }
    else{
        return dp[i][prev]=dynamic(i+1,arr[i],arr);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n>>m;
    vector<ll> arr(n);
    for(ll i=0;i<n;i++){
        cin>>arr[i];
    }
    dp.resize(n+1,vector<ll>(m+2,-1));
    ll ans=dynamic(0,0,arr);
    cout<<ans<<endl;
    return 0;
}