279.完全平方数

题目描述

题解

动态规划

状态定义:

dp[i]表示数字i 由几个数的平方相加.

初始化:

新建一个占n+1空间的一维数组, 令dp[i] = i, 含义为一个数i最差的情况也是由i个1相加得来的

状态转移:

for (int j = 1; i - j * j >= 0; j++) {
    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}

代码

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

    return dp[n];
}