Sujal_715's blog

By Sujal_715, history, 6 months ago, In English

I am currently learning dynamic programming and currently struck in a problem of todays leetcode contest question 3, can anyone point out what is wrong with my code and what should be the better aprroach for this problem.
And also how can i improve on these topics ? Problem Link-- Find the Maximum Length of Valid Subsequence II

include <bits/stdc++.h>

int dp[1001][1001]; int n, ku;

int recc(int level, int Rem_required, int prv, vector &v) { if (level == n) return 0;

if (Rem_required != -1 && dp[level][Rem_required] != -1)
    return dp[level][Rem_required];

int ans = recc(level + 1, Rem_required, prv, v);

if (prv == -1) {
    ans = max(ans, 1 + recc(level + 1, Rem_required, v[level], v));
} else if (Rem_required == -1) {
    ans = max(ans, 1 + recc(level + 1, (v[level] + prv) % ku, v[level], v));
} else if ((v[level] + prv) % ku == Rem_required) {
    ans = max(ans, 1 + recc(level + 1, Rem_required, v[level], v));
}


if (Rem_required == -1)
    return ans;

return dp[level][Rem_required] = ans;

}

void maximumLength(vector &nums, int k) { memset(dp, -1, sizeof(dp)); n = nums.size(); ku = k; cout << recc(0, -1, -1, nums) << endl; }

int main() { int nu, k; cin >> nu >> k; vector v(nu); for (auto &val : v) cin >> val; maximumLength(v, k); return 0; }

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this is a 3d question if you memorization you can use tabularization so that you can reduce its space complexity