Explosive Sum

• Time : $O(n^2)$
• Space : $O(n^2)$

c++

using ull = unsigned long long;

ull dp[1000][1000];
ull helper(unsigned int n, unsigned int ma) {
  if(n == 0) return 1;
  ull& res = dp[n][ma];
  if(res) return res - 1;
  res = 1;
  for(unsigned int i = 1; i <= ma and i <= n; i++) {
    res += helper(n-i,i);
  }
  return res - 1;
}
ull exp_sum(unsigned int n) {
  return helper(n,n);
}