동적 계획 - LeetCode279 완전 제곱

정수 n을 정하고 완전한 제곱수를 몇 개 찾아라(예를 들어 1, 4, 9, 16,...)그것들의 합을 n과 같게 하다.너는 완전한 제곱수의 개수를 최소화해야 한다.
예1:
입력: n = 12 출력: 3 설명: 12 = 4 + 4 + 4.예2:
입력: n = 13 출력: 2 해석: 13 = 4 + 9.
동적 계획 상태 전환 방정식: dp[i] = Math.min( dp[i] , dp[i - j * j] + 1 )
Java 코드:
class Solution {
    public int numSquares(int n) {
        if ( n <= 0 ) {
            return 0;
        }
        int dp[] = new int[n+1];
        dp[0] = 0;
        for( int i = 1 ; i <= n ; i++ ) {
            dp[i] = i;
            for( int j = 1 ; j * j <= i ; j++ ) {
                dp[i] = Math.min( dp[i] , dp[i - j * j] + 1 );
            }
        }
        return dp[n];
    }
}

좋은 웹페이지 즐겨찾기