The Power Sum

• Time : O(xn)
• Space : O(xn)

c++

int dp[1000][1000];
int helper(int X, int p, int now) {
    if(dp[X][now] != -1) return dp[X][now];
    if(pow(now, p) > X) return 0;
    if(pow(now, p) == X) return 1;
    int& res = dp[X][now] = helper(X - pow(now, p), p, now + 1) + helper(X, p, now + 1);
    return res;
}
int powerSum(int X, int N) {
    return helper(X, N, 1);
}