[LeetCode] 279. Perfect Squares

😎풀이

1. dp 생성
2. i는 n까지 순회
3. j제곱이 i이하일 때까지 순회
   3-1. 해당 구문으로 가장 가까운 제곱수로 나눌 수 있는 최소의 수가 dp 배열에 적용됨

function numSquares(n: number): number {
    const dp: number[] = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    
    return dp[n];
}