动态规划篇-04：完全平方数

279、完全平方数

状态转移方程

base case

当n = 0 时，和为n的完全平方数的最少数量为0.

明确状态

“原问题或子问题中变化的变量”

在本题中，状态是 “完全平方数的最少数量”。因为当我们选择不同的完全平方数的时候，所需完全平方数的数量会改变

确定选择

“导致“状态”产生变化的行为”

在本题中，“选择”是选用的完全平方数。

定义dp函数

dp(n) ：和为n的完全平方数的最少数量。

这样我们就可以写出状态转移方程：

dp(n) = dp(n - i*i) + 1;

这里使用的还是 [分解问题] 的思路，将问题 ”和为n所需完全平方数的数量“转化为”和为 (n-i*i) 所需完全平方数的数量 “

暴力解法

class Solution {
    public int numSquares(int n) {
        return dp(n);
    }

    private int dp(int n) {
        //base case
        if (n == 0) {
            return 0;
        }
    
        int res = Integer.MAX_VALUE;
        for (int i = 1; i * i <= n; i++) {
            //状态转移方程
            //使用min是因为题目要求“最少”
            res = Math.min(res, dp(n - i * i) + 1);
        }
    
        return res;
    }

}

这时候我们再联系上动态规划篇-00：解题思想与框架中提到的解题框架：

是不是一模一样？都是遍历所有选择，每一个选择都会导致状态的改变。然后根据题意选择最优解

使用了备忘录的自上而下的递归解法

class Solution {
    public int numSquares(int n) {
        // 创建一个数组用于保存已计算过的中间结果
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
    
        return dp(n, memo);
    }

    private int dp(int n, int[] memo) {
        //base case
        if (n == 0) {
            return 0;
        }
    
        // 如果已经计算过，直接返回保存的结果
        if (memo[n] != -1) {
            return memo[n];
        }
    
        int res = Integer.MAX_VALUE;
        for (int i = 1; i * i <= n; i++) {
            res = Math.min(res, dp(n - i * i, memo) + 1);
        }
    
        // 将计算结果保存到数组中
        memo[n] = res;
    
        return res;
    }
}

使用了dp数组的自下而上的迭代解法

class Solution {
   public int numSquares(int n) {
       int[] dp = new int[n + 1];
       Arrays.fill(dp, Integer.MAX_VALUE);
        //base case
       dp[0] = 0;
    
       for (int i = 1; i <= n; i++) {
           for (int j = 1; j * j <= i; j++) {
               dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
           }
       }
    
       return dp[n];
    }
}