Leetcode:279. Perfect Squares

Posted on | Comments: | Views:
DP

279. Perfect Squares

题目理解:

给出一个数n, 找出最少的平方数的个数, 他们的和为n

思路:

用 f[i][j] 记录状态, 表示找到平方数的最少个数; i 表示的是用 1, 4, …, i^2 这些数来找平方数; j 表示要找的和; 那么问题的答案就是 f[sqrt(n)][n] 了


对于第i个平方数, 考虑取不取它, 分为两种情况, 如果取, 那么相当于n减小, 继续在i个平方数里找; 若不取第i个平方数, 那么就是从i-1个平方数里找; 这样就能够写出状态转移方程 f[i][j] = min{ f[i-1][j], 1+f[i][j-i*i] }


然后实现的时候需要注意细节部分, 比如边界状态, f[0][0] = 0, 但 f[0][j] = ∞ (j!=0), 这里自己思考一下就能明白; 然后选择是否取第i个平方数时, 要考虑j是否足够大, 不然就越界了, 而且实际上与问题也不符

小结:

算是简单的动态规划题, 可重复背包的变种, 但是思考起来感觉容易打岔, 也不能很好的明白这样做是不是对的, 可能还需要多加练习

Submission Detail:

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int f[110][10500];
    int numSquares(int n) {
        for (int i = 0; i <= n; ++i) {
            f[0][i] = 2147483647;
        }
        f[0][0] = 0;
        for (int i = 1; i <= (int)sqrt(n); ++i) {
            for (int j = 0; j <= n; ++j) {
                if (j < i*i) {
                    f[i][j] = f[i-1][j];
                } else {
                    f[i][j] = min(f[i-1][j], f[i][j-i*i]+1);
                }
            }
        }
        return f[(int)sqrt(n)][n];
    }
    int min(int a, int b) {
        if (a > b) {
            return b;
        } else {
            return a;
        }
    }
};