解题报告-Perfect Squares

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.

解题思路:

第一种方案: 二维dp

和为n的数，要么以1开头，要么以4开头，要么以9开头，依次类推，本题就是求这些可能方案中，需要平方数个数最少的那组解

dp[k][n] - 表示以k开头的平方数序列，和为n时，最少需要的平方数个数

进一步递推可得

dp[k][n] = 1 + min{dp[k][n - k], dp[nextK][n - k], ...}

因为，取k是一步，取完k之后，问题变为求解和为n - k的最优解, 我们可以继续取k, 即dp[k][n - k], 或者我们直接取下一个k, dp[nextK][n - k], ....,

最终找到和为n - k时的最优解, 对解加1，即为和为n时，以k开头的最优解.

最终，我们遍历dp[i][n] i = 1, 4, 9, ..., n ，即可以得到和为n的解.

空间复杂度o(n^2) 时间复杂度o(n^3)

空间上我们可以进一步优化，不要从1开始存储到n，优化为只存储平方数

java代码

class Solution {

    //for example

    //n n - 1 n - 2

    //dp[n][num] = 1 + mim{dp[n][num - n], dp[n - 1][num - n], dp[n - 2][num - n], ..., dp[1][n]}

    //ans = min {dp[k][sum]} k = 1,2,3,...,n-1,n

    public int numSquares(int n) {

        int ans = Integer.MAX_VALUE;

        List<Integer> data = new ArrayList<>();

        int i = 0;

        for (; i * i <= n; i++) {

            data.add(i * i);

        }

        if (i * i == n) return 1;

        int cnt = data.size();

        int[][] dp = new int[cnt][1 + n];

        for (int l = 1; l < cnt; l++) {

            for (int p = 1; p <= n; p++) {

                dp[l][p] = Integer.MAX_VALUE;

            }

        }

        for (int k = 1; k < cnt; k++) {

            int val = data.get(k);

            for (int sum = val; sum <= n; sum++) {

                for (int j = k; j >= 1; j--) {

                    if (dp[j][sum - val] == Integer.MAX_VALUE) continue;

                    //System.out.println("k={}" + k + " sum=" + sum + " j={}" + j + " remain={}" + (sum - k));

                    dp[k][sum] = Math.min(dp[k][sum], 1 + dp[j][sum - val]);

                    //System.out.println("dp[k][sum]=" + dp[k][sum]);

                }

            }

            if (ans > dp[k][n]) {

                //System.out.println("dp[k][n]=" + dp[k][n]);

                ans = dp[k][n];

            }

        }

        return ans;

    }

    public boolean isSquare(int d) {

        int i = 1;

        for (; i * i < d; i++) {

        }

        if (i * i == d) return true;

        return false;

    }

}

c++代码

class Solution {

public:

    //dp[i][j] = 1 + min{dp[i][j - i], dp[nextI][j - i], ..., dp[k][j]}

    //dp[i][i] = 1 + min{dp[0][0]} = 1

    //dp[i][j] = 1 + min{dp[i][j - i], dp[ni][j - i], ..., dp[nii][j - i]}

    //if i > j, dp[i][j] = INT_MAX;

    //if i == j, dp[i][j] = 1;

    //if i < j,

    //

    int numSquares(int n) {

        int i = 1;

        vector<int> data;

        while (i * i <= n) {

            data.push_back(i * i);

            ++i;

        }

        int len = data.size();

        int dp[1 + len][1 + n];

        memset(dp, 0, sizeof(dp));

        int ans = INT_MAX;

        //cout<<"len="<<len<<endl;

        for (int i = 1; i <= len; i++) {

            //cout<<"num="<<data[i - 1]<<endl;

            for (int j = data[i - 1] - 1; j >= 1; j--) {

                dp[i][j] = INT_MAX;

                //output(i, j, dp[i][j]);

            }

        }

        for (int j = 1; j <= n; j++) {

            for (int i = 1; i <= len && data[i - 1] <= j; i++) {

                int tmp = INT_MAX;

                for (int k = i; k <= len; k++) {

                    tmp = min(tmp, dp[k][j - data[i - 1]]);

                }

                //output(i, j, tmp);

                if (tmp != INT_MAX) {

                    dp[i][j] = 1 + tmp;

                } else {

                    dp[i][j] = tmp;

                }

                //output(i, j, dp[i][j]);

            }

        }

        for (int i = 1; i <= len; i++) {

            ans = min(ans, dp[i][n]);

            //cout<<"ans="<<ans<<endl;

        }

        return ans;

    }

    void output(int i, int j, int tmp) {

        cout<<"i="<<i<<" j="<<j<<" tmp="<<tmp<<endl;

    }

    void output2(int i, int j, int tmp) {

        cout<<"output2 i="<<i<<" j="<<j<<" tmp="<<tmp<<endl;

    }

};

第二种解法：一维dp

思路: dp[n] = 1 + min{dp[n - i * i]} n - i * i >= 0

想使和为n，则最后一步使用的平方数可以为 1, 或者 4 或者 9, 即最后一步可以使用 i * i

则把所有可能枚举出来，求1 + min{dp[n - i * i]}

java代码

class Solution {

    //dp[i] = min{dp[i - j * j]} i - j * j >= 0

    public int numSquares(int n) {

        List<Integer> dp = new ArrayList<>();

        for (int i = 0; i <= n; i++) {

            dp.add(Integer.MAX_VALUE);

        }

        dp.set(0, 0);

        for (int i = 1; i <= n; i++) {

            int j = 1;

            while (i - j * j >= 0) {

                if (dp.get(i - j * j) != Integer.MAX_VALUE) {

                    dp.set(i, Math.min(dp.get(i), 1 + dp.get(i - j * j)));

                }

                ++j;

            }

        }

        return dp.get(n);

    }

}

c++代码

class Solution {

public:

    //dp[n] = min{dp[n - i*i]} i*i<=n

    //dp[n] represent least number of perfect square numbers

    //dp[0] = 0, dp[1] = 1, dp[2] = dp[1] + 1 = 2

    int numSquares(int n) {

        int dp[1 + n];

        for (int i = 0; i < n + 1; i++) {

            dp[i] = INT_MAX;

        }

        dp[0] = 0;

        for (int i = 1; i <= n; i++) {

            int j = 1;

            while (i - j * j >= 0) {

                if (dp[i - j * j] != INT_MAX) {

                    //cout<<dp[i]<<" "<<dp[i - j * j]<<endl;

                    dp[i] = min(dp[i], 1 + dp[i - j * j]);

                    //cout<<"dp[i]="<<dp[i]<<endl;

                }

                ++j;

            }

        }

        /*

        for (int d : dp) {

            cout<<d<<endl;

        }

        */

        return dp[n];

    }

};

巴特西

解题报告-Perfect Squares

最新文章

热门文章