本文主要是介绍leetcode279: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.
题目分析：属于离散背包问题，背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。本题计算在n时，可以为n-j*j的值加1，这样的话就可以考虑使用动态规划。当当前值跟之前的值有一定的联系的时候，我们可以考虑使用动态规划。
具体代码如下
public int numSquares(int n) {if(n<=0) return 0;int[] dp=new int[n+1];dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){int min=Integer.MAX_VALUE;int j=1;//找到合适的j,当j*j<=i时可以不断尝试while(j*j<=i){if(j*j==i){min=1;break;}//更新minmin=Math.min(min, dp[i-j*j]+1);j++;}dp[i]=min;}return dp[n];}这篇关于leetcode279:Perfect Squares的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
