Array Description

I was trying this question on CSES. Everytime I start dp problem by thinking recursively. I did the same here, but my recursive solution isn’t working and I am not able to figure out why. So it will be very helpful if one can have a look at my code.

#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vc vector<char>
#define vii vector<vi>
#define mp make_pair
#define vpi vector< pair<int, int> >
#define take_input freopen("input.txt", "r", stdin)
#define give_output freopen("output.txt", "w", stdout)
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fi first
#define se second
#define mod 1000000007
#define min_pql priority_queue< int, vector<int>, greater<int> >

using namespace std;
using namespace std::chrono;

int solve(int n, int m, vi &arr, int i=0) {
    if(i == n) return 1;
    int cnt=0;
    if(arr[i] == 0) {
        if(i==0) {
            if( i+1<n && arr[i+1]!=0) {
                for(int j=-1; j<=1; j++){
                    if( (arr[i+1]+j>=1) && (arr[i+1]+j<=m)) {
                        arr[i] = arr[i+1]+j;
                        cnt += solve(n, m, arr, i+1);
                        arr[i] -= (arr[i+1]+j);
                    }
                }
            } else {
                for(int j=1; j<=m; j++){
                    arr[i] = j;
                    cnt += solve(n, m, arr, i+1);
                    arr[i] -= j;
                }
            } 
        } else {
            set<int> ind;
            if(i+1<n && arr[i+1] != 0) {
                for(int j=-1; j<=1; j++){
                    ind.insert(arr[i+1]+j);
                    ind.insert(arr[i-1]+j);
                }
            } else {
                for(int j=-1; j<=1; j++) {
                    ind.insert(arr[i-1]+j);
                }
            } 
            for(int x:ind) {
                arr[i] = x;
                if(x>=1 && x<=m) cnt += solve(n, m, arr, i+1);
                arr[i] -= x;
            }
        }
    } else {
        cnt += solve(n, m, arr, i+1);
    }
    return cnt;

}

int32_t main(){
    fastIO;
    //take_input;
    //give_output;
    int n, m; cin >> n >> m;
    vi arr(n);
    for(int &i:arr) cin >> i;
    cout << solve(n, m, arr);
}

Same Here!!

I also stuck in the same problem.
my program gives correct output in lower range but for higher range it gives WA.
I don’t know exactly what’s wrong in your code but maybe I can explain my intuition , by which you can get an idea .
my code https://cses.fi/paste/bfc818186c52bd982933be/


Well, here is my explanation for input
2 2
0 1
Here, the valid array would be
2 1
1 1
note: I have taken an array of size n+1 (assigning the element in array from index 1 to n)

total method dp(n,1)+dp(n,2)+dp(n,3)…dp(n,m)

a particular state dp(i,x) is possible if at index i-1 we get x-1||x||x+1

means dp(i-1,x-1)+dp(i-1,x)+dp(i-1,x+1)

recursion tree

If anyone have solve this problem using top-down approach, then, Please help!!

Finally solved it.

Recursive Code: https://cses.fi/paste/be9b8cc2a7103fea296010/

Iterative Code: https://cses.fi/paste/bf81fc70261c49e5295ffa/