确定用作状态转移的dp数组的下标及含义 dp[j] 整数n为j时 和为j的完全平方数的最少数量
class Solution {
public:
int numSquares(int n) {
// 设置成INT_MAX-1 防止dp[j-i*i]+1 整数越界
std::vector<int> dp(n + 1, INT_MAX - 1);// 背包大小
// dp[j-i*i] + 1 = dp[0] + 1 = 1 当 j = i*i
dp[0]=0; // 多增加 dp[0]=0 为了递推公式
for (int i=0;i*i<n+1;i++) // 遍历物品
// 此处j不能从1开始，避免dp[j-i*i]下标负数
for (int j=i*i;j<n+1;j++) //遍历背包
dp[j] = std::min(dp[j-i*i]+1, dp[j]);
return dp[n];
}
};