LeetCode 279 Perfect Squares (Tags:DP)

LeetCode 279 Perfect Squares

1.问题描述

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

翻译过来就是给定一个数，找到一组完全平方数，其和等于给定的数。而且要求这一组完全平方数的个数最少。

2. 思路

• 定义dp[] 数组，dp[i]表示 给定i时perfect square 的数目。
• dp[0] = 0
• dp[1] = dp[0] + 1
• dp[2] = dp[1] + 1
• dp[3] = dp[2] + 1
• dp[4] = Min{dp[4 - 1 * 1] + 1 , dp[4 - 2 * 2] + 1} = 1
• dp[5] = Min{dp[5 - 1 * 1] + 1, dp[5 - 2 * 2] + 1} = 2
• dp[n] = Min{dp[n - 1 * 1] + 1, dp[n - 2 * 2] + 1, ...}

3. 代码

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 = 1; i <= n; ++i) {
           int min = Integer.MAX_VALUE;
           int j = 1;
           while(i - j * j >= 0) {
               min = Math.min(min, dp[i - j * j] + 1);
               ++j;
           }
           dp[i] = min;
       }
       return dp[n];
   }

}