leetcode279和四平方和定理

前言

数论问题

正文

问题来源

本问题来自leetcode上的279题。由于本人做题时选择动态规划的题目做，既然有动态规划这么明显的提示，我也是很快的就解出了这道题，但是这个问题没有想象中那么简单，还是太naive了！

问题描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

分析：

由于这道题被分到动态规划类问题中了，很容易就会想到用动态规划来解这道题。由于这道题的状态转移方程。不难得到如下公式：

dp[i] =min(dp[i-j*j]);//(取值范围0<j<=sqrt(i))

C代码如下所示：(爱手撸C，呵呵)

#define min(x,y) ((x)<(y)?(x) : (y))
int numSquares(int n) {
    int *dp = NULL;
	int i,j,m;
	int ret;
	dp = (int *)malloc((n+1)*sizeof(int));
	dp[0] = 0;
	for(i=1;i<=n;i++)
	{
		j=(int)sqrt(i);
		m = dp[i-j*j];
		for(j=j-1;j>0;j--)
		{
			m = min(m,dp[i-j*j]);
		}
		dp[i] = m+1;
	}
	ret = dp[n];
	free(dp);
	return ret;
}

结果提交后，发现自己仅仅打败了百分之八十几的对手，这道题还有最优解。 leetcode官方给出的最优解如下：

int numSquares(int n) {
    while (n % 4 == 0)
        n /= 4;
    if (n % 8 == 7)
        return 4;
    for (int a=0; a*a<=n; ++a) {
        int b = (int)sqrt(n - a*a);
        if (a*a + b*b == n)
            return a == 0 ? 1 : 2;
    }
    return 3;
}

索性查了查资料，原来这道题是与数学问题有关。Lagrange’s four-square theorem四平方和定理（恕在下才疏学浅，还是那句老话，数学还是计算机之母） ####四平方和定理

reference：Lagrange’s four-square theorem
这里算是完全用数学知识解决了这个问题。解这题全靠这个公式：

(8*m+7)*4^k

这个定理就是讲，任何数都可以由4个平方数组成，即 n = a^2 + b^2 + c^2 + d^2，所以这题的答案已经限定在了 [1,4] 之间。而上面这个公式的发明者－Adrien-Marie Legendre 又补充了这个定理：除了满足以上这个公式的数以外的任何数都可以由3个平方数组成。所以，这个答案又可以缩小范围了。范围都已经缩小到 [1,3] 了，我们开始求解。

结语

见多才会遇事不慌。虽然这道题暴力也是可以解决的，作为程序员需要一颗时常想着优化的心。

leetcode279 And Four-square Theorem

前言

正文

问题来源

问题描述

分析：

结语

CATALOG

FEATURED TAGS