I'm new to this forum and this is my first post . I'm beginning to understand DP, and would really like your help in solving CZ_PROB1.
As a first step, I've precomputed all primes till 8000 that are sums of two squares (i.e. Sp2(n) in the problem).
Now, for calculating p(n,k), I'm failing to come up with the DP substructure. I don't see how p(n,k) is related to p(n,k-1) or p(n-1,k). Can someone help me please?
I do see that p(n,1) = 1 - not sure how to proceed from there.
Thanks a lot in advance!