Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

这道题上来就想到的DP,DP[i]表示到第i个数字的最小sum of square numbers. 设w[j]为第j个square number, 转移方程为 DP[i] = min { DP[i  – w[j]], DP[i – 1]} + 1,最后输出DP[n]就好了。

e.g. 12的DP表

1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 1 2 3 4 2 1 2 3 3

C++ Solution


class Solution {
public:
        int w[100000];
        int DP[100000];
        int numSquares(int n) {
                int wi = sqrt(n) + 1;
                int tempMinNum;
                DP[0] = 0;

                for(int i = 2; i <= wi; ++i)  w[i - 1] = pow(i, 2);

                for(int i = 1; i <= n; ++i)
                {
                        int minNum = (1<<31) - 1;

                        for(int j = 1; j <= wi; ++j)
                        {
                                if(i < w[1]) { DP[i] = DP[i - 1] + 1; break; }
                                if(i < w[j]) { DP[i] = minNum; break; }
                                tempMinNum = min(DP[i - w[j]] + 1, DP[i - 1] + 1);
                                if(tempMinNum < minNum) minNum = tempMinNum;
                        }
                }
                return DP[n];
        }
};

最后的提交结果虽然AC但很让人不解的是运行速度只有40%,想了半天也没什么思路于是上网查了下发现这其实是道数学题,用到的是四平方定理。
简单说就是任何正整数都可以表示为四个整数的平方和(其实是小于等于4个),具体的解释和代码参见:http://www.cnblogs.com/grandyang/p/4800552.html

 

Update on 2/18/2016

今天又想了下,发现其实这题的DP还有个很tricky的做法,就是把DP在第一次运行的时候就预计算到一个DP array里,然后后面每次直接取值就好了。。所以后面每次时间复杂度都是O(1)。。


int DP[10000];
bool precom = true;

class Solution {
public:
        int w[10000];
        int numSquares(int num) {
                if(!precom) return DP[num];

                int n0 = 10000;
                int wi = sqrt(n0) + 1;
                int tempMinNum;
                DP[0] = 0;

                for(int i = 1; i <= wi; ++i)
                        w[i - 1] = pow(i, 2);

                for(int i = 1; i <= n0; ++i)
                {
                        int minNum = 2147483647;

                        for(int j = 1; j <= wi; ++j)
                        {
                                if(i < w[1]) { DP[i] = DP[i - 1] + 1; break; }
                                if(i < w[j]) { DP[i] = minNum; break; }
                                tempMinNum = min(DP[i - w[j]] + 1, DP[i - 1] + 1);
                                if(tempMinNum < minNum) minNum = tempMinNum;
                        }
                }
                precom = false;
                return DP[num];
        }
};

这段代码的运行时间为12ms,远远快于每次都重新计算的速度(其实确实完全没必要重新算)

Leave a Reply

Your email address will not be published. Required fields are marked *