Please help me with CSES - Array Description (top-down approach)

general
, ,
1

I got TLE on the 27 tc, maybe the loop inside the function is the problem but i don’t know how to optimize it.


#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define ll long long int
#define ull unsigned long long
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vp vector <pii>
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define ef emplace_front
#define eb emplace_back
#define f first
#define s second
using namespace std;
 
int dp[(int) 1e5 + 3][101];
 
int solve(int ind, int prev, int m, int a[]){
    if (ind < 0){
        return 1;
    }
    if (dp[ind][prev] != -1) return dp[ind][prev]; 
    int ans = 0;        
    if (a[ind] != 0){
        if (abs(a[ind] - prev) <= 1) return dp[ind][prev] = solve(ind - 1, a[ind], m, a) % mod;
        else return 0;
    }
    else{
        for (int i = 1; i <= m; i++){
            if (abs(prev - i) <= 1) ans += solve(ind - 1, i, m, a) % mod; 
        }
    }
    return dp[ind][prev] = ans % mod;
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // freopen("input.inp", "r", stdin);
    // freopen("output.out", "w", stdout);
    mem(dp, -1);
    int n, m; cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
        int ans = 0;
    if (a[n - 1] == 0){
        for (int i = 1; i <= m; i++){
            ans += solve(n - 2, i, m, a) % mod;
        }
        cout << ans % mod;
    }
    else{
        ans = solve(n - 2, a[n - 1], m, a);
        cout << ans;
    }
}