LeetCode Q279: Perfect Squares

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.

Solutions:

Using DP. For many detailed explanation please refer to: https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics

One of trick to use is so called "Static DP", which use a static vector to save already computed results among huge number of test cases to same more time. But for single call, it is no difference to what I present here.

	class Solution {
	public:
	int numSquares(int n) {
	if(n<=0) return 0;
	vector<int> M(n+1, INT_MAX);
	M[0]=0;
	for(int i=1; i<=n; i++)
	for(int j=1; j*j<=i; j++)
	M[i]=min(M[i], M[i-j*j]+1);
	return M.back();
	}
	};

view raw Q279.cpp hosted with ❤ by GitHub

Round 3:

	class Solution {
	public:
	int numSquares(int n) {
	vector<int> myT(n+1, INT_MAX);
	myT[0]=0;
	for(int i=1; i<=n; i++){
	for(int j=1; j*j<=i; j++)
	myT[i] = min(myT[i], myT[i-j*j]+1);
	}
	return myT.back();
	}
	};

view raw Q279Rnd3.cpp hosted with ❤ by GitHub