Help needed with memoizing a recursive solution

Debugging Help
#1

Problem: Hoof, Paper, Scissors
Initially, I wrote a recursive solution to the problem, and it passed the sample test cases. When I try to memoize the same solution, it produces different output.

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

#define int long long
#define vt vector

typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ld, ld> pd;

typedef vt<int> vi;
typedef vt<ld> vd;
typedef vt<pi> vpi;
typedef vt<string> vs;
typedef vt<vi> vvi;

#define r_ep(i, a, b, s) for(int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define rep1(e) r_ep(i, 0, e, 1)
#define rep2(i, e) r_ep(i, 0, e, 1)
#define rep3(i, b, e) r_ep(i, b, e, 1)
#define rep4(i, b, e, s) r_ep(i, b, e, s)
#define get5(a, b, c, d, e, ...) e
#define repc(...) get5(__VA_ARGS__, rep4, rep3, rep2, rep1)
#define rep(...) repc(__VA_ARGS__)(__VA_ARGS__)
#define each(i, a) for (auto &i: a)

#define all(x) (x).begin(), (x).end()
#define amin(a, b) a = min(a, b)
#define amax(a, b) a = max(a, b)
#define sz(x) (int) (x).size()
#define bg(x) (x).begin()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fr first
#define sc second
#define lb lower_bound
#define ub upper_bound

string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char * s) { return string(s); }
string to_string(string s) { return s; }
template<class A, class B>
string to_string(pair<A, B> &a) { 
  return to_string(a.fr) + " " + to_string(a.sc); 
}

template<class T> void read(T &x) { cin >> x; }
void read(float &d) { string t; read(t); d = stof(t); }
void read(double &d) { string t; read(t); d = stod(t); }
void read(ld &d) { string t; read(t); d = stold(t); }
template<class A, class B> void read(pair<A, B> &a) {
  read(a.fr); read(a.sc);
}
template<class A> void read(vt<A> &a) { each(i, a) read(i); }
template<class H, class... T> void read(H &h, T&... t) {
  read(h); read(t...);
}

template<class T> void write(T x) { cout << to_string(x); }
template<class H, class... T> void write(const H &h, const T&... t) {
  write(h); write(t...); 
}

void print() { write("\n"); }
template<class T> void print(vt<T> x) { 
  each(i, x) { write(i); write(" "); }
  print();
}
template<class H, class... T> void print(const H &h, const T&... t) {
  write(h); if (sizeof...(t)) write(' '); print(t...);
}

template <class T1, class T2>
ostream &operator<< (ostream &os, const pair<T1,T2> &p) {
  os << '{' << p.first << ", " << p.second << '}';
  return os;
}

template <typename C, 
typename T = std::decay_t<decltype(*begin(std::declval<C>()))>,
typename std::enable_if<!std::is_same<C, std::string>::value>::type* = nullptr>
ostream &operator<<(ostream &os, const C &container) {
  bool first = true;
  stringstream ss; 
  ss << '[';
  for(const auto &x : container) {
    if (!first) {
      ss << ", ";
    }
    first = false;
    ss << x;
  }
  ss << ']';
  return os << ss.str();
}

#ifndef ONLINE_JUDGE
  #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
  template <typename Arg1>
  void __f(const char* name, Arg1&& arg1) {
    cerr << name << " : " << arg1 << '\n';
  }
  template <typename Arg1, typename... Args>
  void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1<<" | ";
    __f(comma + 1, args...);
  }
#else
  #define debug(...)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void setIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

int lcm(int a, int b) { return a / __gcd(a, b) * b; }
int ceil(int n, int d) { return (n - 1) / d + 1; }

const char nl = '\n';
const int mod = 1e9 + 7;
string gestures = "RPS";

int result(char opp_gesture, char gesture) {
  if (gesture == 'R') {
    return opp_gesture == 'S';
  } else if (gesture == 'P') {
    return opp_gesture == 'R';
  }
  return opp_gesture == 'P'; 
}

int max_wins(vt<char> &a, char gesture, int n, int k) {
  if (n == 0) return 0;
  
  // switch the gesture
  int mx1 = INT_MIN;
  if (k > 0) {
    each(i, gestures) {
      if (i == gesture) continue;
      amax(mx1, max_wins(a, i, n - 1, k - 1));
    }
  }

  // don't switch the gesture
  int mx2 = max_wins(a, gesture, n - 1, k);
  
  int ans = max(mx1, mx2) + result(a[n - 1], gesture);
  return ans;
}

void solve() {
  int n, k; read(n, k);
  vt<char> a(n); read(a);
  each(i, a) if (i == 'H') i = 'R';
  int mx = INT_MIN;
  each(i, gestures) {
    amax(mx, max_wins(a, i, n, k));
  }
  print(mx);
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  setIO("hps");

  int tc = 1;
  // read(tc);
  rep(i, 1, tc + 1) {
    // write("Case #", i, ": ");
    solve();
  }

  return 0;
}
Incorrect Memoized Solution 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vt vector

typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ld, ld> pd;

typedef vt<int> vi;
typedef vt<ld> vd;
typedef vt<pi> vpi;
typedef vt<string> vs;
typedef vt<vi> vvi;

#define r_ep(i, a, b, s) for(int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define rep1(e) r_ep(i, 0, e, 1)
#define rep2(i, e) r_ep(i, 0, e, 1)
#define rep3(i, b, e) r_ep(i, b, e, 1)
#define rep4(i, b, e, s) r_ep(i, b, e, s)
#define get5(a, b, c, d, e, ...) e
#define repc(...) get5(__VA_ARGS__, rep4, rep3, rep2, rep1)
#define rep(...) repc(__VA_ARGS__)(__VA_ARGS__)
#define each(i, a) for (auto &i: a)

#define all(x) (x).begin(), (x).end()
#define amin(a, b) a = min(a, b)
#define amax(a, b) a = max(a, b)
#define sz(x) (int) (x).size()
#define bg(x) (x).begin()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fr first
#define sc second
#define lb lower_bound
#define ub upper_bound

string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char * s) { return string(s); }
string to_string(string s) { return s; }
template<class A, class B>
string to_string(pair<A, B> &a) { 
  return to_string(a.fr) + " " + to_string(a.sc); 
}

template<class T> void read(T &x) { cin >> x; }
void read(float &d) { string t; read(t); d = stof(t); }
void read(double &d) { string t; read(t); d = stod(t); }
void read(ld &d) { string t; read(t); d = stold(t); }
template<class A, class B> void read(pair<A, B> &a) {
  read(a.fr); read(a.sc);
}
template<class A> void read(vt<A> &a) { each(i, a) read(i); }
template<class H, class... T> void read(H &h, T&... t) {
  read(h); read(t...);
}

template<class T> void write(T x) { cout << to_string(x); }
template<class H, class... T> void write(const H &h, const T&... t) {
  write(h); write(t...); 
}

void print() { write("\n"); }
template<class T> void print(vt<T> x) { 
  each(i, x) { write(i); write(" "); }
  print();
}
template<class H, class... T> void print(const H &h, const T&... t) {
  write(h); if (sizeof...(t)) write(' '); print(t...);
}

template <class T1, class T2>
ostream &operator<< (ostream &os, const pair<T1,T2> &p) {
  os << '{' << p.first << ", " << p.second << '}';
  return os;
}

template <typename C, 
typename T = std::decay_t<decltype(*begin(std::declval<C>()))>,
typename std::enable_if<!std::is_same<C, std::string>::value>::type* = nullptr>
ostream &operator<<(ostream &os, const C &container) {
  bool first = true;
  stringstream ss; 
  ss << '[';
  for(const auto &x : container) {
    if (!first) {
      ss << ", ";
    }
    first = false;
    ss << x;
  }
  ss << ']';
  return os << ss.str();
}

#ifndef ONLINE_JUDGE
  #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
  template <typename Arg1>
  void __f(const char* name, Arg1&& arg1) {
    cerr << name << " : " << arg1 << '\n';
  }
  template <typename Arg1, typename... Args>
  void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1<<" | ";
    __f(comma + 1, args...);
  }
#else
  #define debug(...)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void setIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

int lcm(int a, int b) { return a / __gcd(a, b) * b; }
int ceil(int n, int d) { return (n - 1) / d + 1; }

const char nl = '\n';
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int dp[N][30];
string gestures = "RPS";

int result(char opp_gesture, char gesture) {
  if (gesture == 'R') {
    return opp_gesture == 'S';
  } else if (gesture == 'P') {
    return opp_gesture == 'R';
  }
  return opp_gesture == 'P'; 
}

int max_wins(vt<char> &a, char gesture, int n, int k) {
  if (n == 0) return 0;
  
  if (dp[n][k] != -1) return dp[n][k];

  // switch the gesture
  int mx1 = INT_MIN;
  if (k > 0) {
    each(i, gestures) {
      if (i == gesture) continue;
      amax(mx1, max_wins(a, i, n - 1, k - 1));
    }
  }

  // don't switch the gesture
  int mx2 = max_wins(a, gesture, n - 1, k);
  
  int ans = max(mx1, mx2) + result(a[n - 1], gesture);
  return dp[n][k] = ans;
}

void solve() {
  int n, k; read(n, k);
  vt<char> a(n); read(a);
  each(i, a) if (i == 'H') i = 'R';
  int mx = INT_MIN;
  each(i, gestures) {
    memset(dp, -1, sizeof(dp));
    amax(mx, max_wins(a, i, n, k));
  }
  print(mx);
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  // setIO("");

  int tc = 1;
  // read(tc);
  rep(i, 1, tc + 1) {
    // write("Case #", i, ": ");
    solve();
  }

  return 0;
}

I tried debugging the code and it seems that the optimal answer for any value of n, k is different in both the solutions.

Left image: results of recursive solution, Right image: results of memorized solution

doubt
doubt887×727 117 KB

I tried printing the values of n, k, and dp[n][k] for each state but it doesn’t match with the ones from the recursive solution. I don’t know the exact reason why this is happening. Am I missing something?

#2

I suggest you go over the recusive solution and on paper think step by step what’s going on so you can understand and not memorize it which would will help you in the long run. Try using debugger on your IDE (if there is one for you).