Auto comment: topic has been updated by YogayoG (previous revision, new revision, compare).

I came up with following solution. It uses the fact that either minimal summand in the partition or ammount of summands is not too big. Let arrange the summands in the partition in the non decreasing order. Denote f(i, j) — number of partitions of number i if the minimal summand is j, g(i, j) — number of partitions of number i if the amount of summands is j. Then f(i, j) = f(i - j, j) + f(i, j + 1) (we either put j as a new summand or increase the minimal summand), g(i, j) = g(i - 1, j - 1) + g(i - j, j) (we either put 1 as a new summand or we will have all the summands are greater than 1 then decrease all of them by 1 and return to the state when all the summands are greater or equal than 1). Let p be such number that (p - 1) * (p - 1) ≤ n, p * p > n. Let s = p - 1. We compute values of g(i, j) for all i = 1...n, j = 1...s. Then lets calculate values of f(i, p) for all i = 1...n. Iterate through the number of summand here and express it through the fungtion g: . Then we can calculate values of f(i, j) for all i = 1...n, j = 1...s. Time and space complexity are . It seems pretty amazing to me that there is such a solution while before I encountered with such a problem and didn't know that it's possible to solve it with such complexity. Is it known that we can solve this problem with such complexity or better?

On the OEIS page, the formula involving A001318 looks like it yields an solution if addition and subtraction are O(1) (e.g., modulo an integer).

Edit: this is essentially the same as bciobanu's comment above.