LIKE CODING: MJ [14] Number of square sum partitions

LIKE CODING: MJ [14] Number of square sum partitions
Given a number n, find number of ways to express n by a sum of squares. Eg., if n=8, n can be expressed as 1+1+1+1+1+1+1+1, 4+4, or 4+1+1+1+1. So it should return 3.

Method1:

1. find all the squares not greater than n and construct vec
2. follow the idea of Coin Change [3] to find the number of ways

    int getPartitions(int n){

        int m = sqrt(n);

        vector<int> vec(m);

        for(int i=1; i<=m; ++i){

            vec[i-1] = i*i;

        }

 

        vector<int> dp(n+1);

        dp[0] = 1;

        for(int i=0; i<m; ++i){

            for(int j=1; j<=n; ++j){

                dp[j] += (j-vec[i]>=0)?dp[j-vec[i]]:0;

            }

        }

        return dp[n];

    }

Read full article from LIKE CODING: MJ [14] Number of square sum partitions