perfect squares

Perfect Squares
min[i]表示数字i所需的最少的perfect square.
我们可以得到这样的状态关系 min[i] = min(min[i], min[i - j × j] + 1)
注意，如果i - j×j == 0, 那么min[i] = 1，所以初始化的时候，min[0] = 0; j从1开始计数.

public int (int n) {
    int[] min = new int[n + 1];
    min[0] = 0;
    for (int i = 1; i <= n; ++i) {
        min[i] = Integer.MAX_VALUE;
        for (int j = 1; j * j <= i; ++j) {
            min[i] = Math.min(min[i], min[i - j * j] + 1);
        }
    }
    return min[n];
}

perfect squares

近期文章

近期评论

标签

热门

文章归档

分类目录

功能