Recursive DP Without Fighting Memoization

Recursive DP is at its best when the state is obvious and the memoization is boring.

Start from the state

Before writing the recurrence, name the state in plain language.

For example, dp(i, sum) might mean:

The number of ways to use suffix i..n-1 and reach the remaining sum.

That sentence is more valuable than the code template.

Then write the recurrence

int solve(int i, int remaining) {
  if (remaining == 0) return 1;
  if (i == n || remaining < 0) return 0;
 
  int &answer = memo[i][remaining];
  if (answer != -1) return answer;
 
  answer = solve(i + 1, remaining);
  answer += solve(i + 1, remaining - a[i]);
  return answer;
}

Keep memoization visible

Hiding memoization can be elegant, but for contests, explicit tables are easier to debug under pressure.