当前位置:网站首页>【Leetcode刷题篇】leetcode279 完全平方数

【Leetcode刷题篇】leetcode279 完全平方数

2020-12-06 20:20:02 mind_programmonkey

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

示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

示例 2:输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解题思路:
在这里插入图片描述

class Solution {
    
    public int numSquares(int n) {
    
        // 动态规划
	    	int[] dp = new int[n+1];// 默认初始化值都为0
	    	for(int i=1;i<=n;i++) {
    
	    		// 最坏的情况就是每次都为1相加
	    		dp[i] = i;
	    		// 对其更新
	    		for(int j=1;i-j*j>=0;j++) {
    
	    			dp[i] = Math.min(dp[i],dp[i-j*j]+1);//动态转移方程
	    		}
	    	}
	    	return dp[n];
    }
}

版权声明
本文为[mind_programmonkey]所创,转载请带上原文链接,感谢
https://codingchaozhang.blog.csdn.net/article/details/110735230