按平方数来分割整数
279. Perfect Squares(Medium)
题目描述:
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
思路分析:
?? 将 n 以内的平方数都求出来, 然后设置数组 dp[i], 表示整数 i 按平方数分割的个数, 则 dp[n] 表示整数 n 按平方数分割的个数, 那么我们可以得到状态转移方程 dp[i]=dp[i-square]+1.
代码:
- public int numSquares(int n){
- List<Integer>squareList=generate(n); // 生成 n 以内的所有平方数
- int []dp=new int[n+1];
- for(int i=1;i<=n;i++){
- int min=Integer.MAX_VALUE;
- for(int square:squareList){
- if(square>i) // 平方数比当前的 n 还大, 那么退出
- break;
- min=Math.min(min,dp[i-square]+1);
- }
- dp[i]=min;
- }
- return dp[n];
- }
- public List<Integer>generate(int n){ // 生成平方数
- List<Integer>res=new ArrayList<>();
- int square=1;
- int diff=3;
- while(square<=n){
- res.add(square);
- square=square+diff;
- diff=diff+2;
- }
- return res;
- }
来源: http://www.bubuko.com/infodetail-3110704.html