Leetcode 279. Perfect Squares

tags: Leetcode(JAVA)

題目 : https://leetcode.com/problems/perfect-squares/ 。

想法 :

​​​​DP ! DP ! DP !
​​​​dp[n]=min(dp[n], dp[n-pow(i,2)]+1);

時間複雜度 : O(n^(2/3))。

程式碼 : (JAVA)

class Solution {
    public int numSquares(int n) {
        int[] dp=new int[n+1];
        
        for(int i=0 ; i<=n ; i++){
            dp[i]=Integer.MAX_VALUE;
        }
        
        dp[0]=0;
        for(int i=1 ; i<=n ; i++){
            for(int j=1 ; j*j <= i ; j++){
                dp[i]=Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        
        return dp[n];
    }
}