郑州网站个人开发线上广告投放渠道

动态规划

• 思路：
  • 假设 dp[i] 为最少组成数 i 的平方数个数；
  • 则其上一个状态为 dp[i - j^2] + 1，1 为 j^2：
    • 即 i 的最少完全平方数 = i - j^2 的最少完全平方数 + 1，其中 j^2  <= i 为最接近 i 的平方数；
  • 初始值：dp[0] = 0
  • 所以，可以通过动态规划算出每一个 dp[i]

class Solution {
public:int numSquares(int n) {std::vector<int> dp(n + 1);dp[0] = 0;for (int i = 1; i <= n; ++i) {int minn = INT_MAX;for (int j = 1; j * j <= i; ++j) {minn = std::min(minn, dp[i - j * j]);}dp[i] = minn + 1;}return dp[n];}
};

——————————————————————————————