美文网首页
279. Perfect Squares

279. Perfect Squares

作者: becauseyou_90cd | 来源:发表于2018-07-26 05:38 被阅读0次

https://leetcode.com/problems/perfect-squares/description/

解题思路:

  1. 两个循环:核心是i + j * j <= n, 对dp[i + j * j]进行更新

代码:

class Solution {
public int numSquares(int n) {

    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 1; i + j * j <= n; j++){
            dp[i+j*j] = Math.min(dp[i+j*j], dp[i] +1);
        }
    }
    return dp[n];
}

}

相关文章

网友评论

      本文标题:279. Perfect Squares

      本文链接:https://www.haomeiwen.com/subject/abmumftx.html