Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 12

Description

Ways to Express an Integer as Sum of Powers

Given two positive integers n and x.

Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1x + n2x + ... + nkx.

Since the result can be very large, return it modulo 109 + 7.

For example, if n = 160 and x = 3, one way to express n is n = 23 + 33 + 53.

Example 1:

Input: n = 10, x = 2
Output: 1
Explanation: We can express n as the following: n = 32 + 12 = 10.
It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.

Example 2:

Input: n = 4, x = 1
Output: 2
Explanation: We can express n in the following ways:
- n = 41 = 4.
- n = 31 + 11 = 4.

Constraints:

• 1 <= n <= 300
• 1 <= x <= 5

Solution

class Solution {
  const int MOD = 1e9 + 7;
  int solve(int pos, int rest, vector<vector<int>> &dp, const vector<int> &powers) {
    if(!rest) return 1;
    if(pos < 0) return 0;
    if(dp[pos][rest] != -1) return dp[pos][rest];
    dp[pos][rest] = 0;
    for(int i = pos; i >= 0; --i) {
      if(powers[i] > rest) continue;
      dp[pos][rest] += solve(i - 1, rest - powers[i], dp, powers);
      dp[pos][rest] %= MOD;
    }
    return dp[pos][rest];
  }
public:
  int numberOfWays(int n, int x) {
    vector<int> powers;
    for(int i = 1; pow(i, x) < n + 1; ++i) {
      powers.push_back(pow(i, x));
    }
    int len = powers.size();
    vector<vector<int>> dp(len, vector<int>(n + 1, -1));
    return solve(len - 1, n, dp, powers);
  }
};

// Accepted
// 1502/1502 cases passed (646 ms)
// Your runtime beats 14.16 % of cpp submissions
// Your memory usage beats 59.48 % of cpp submissions (72.1 MB)