4.完全平方数(最少的)

$dp[i] = Math.min(dp[i],dp[i-j*j]+1);$

• 2.18

  • 忘了 i-j*j 了
  • 寄

• 2.4

  • 难点一：忘了初始化 dp 数组全为最大值，因为有个与当前位置 dp 数组的 min 比较，不像打家劫舍
  • 难点二：内 for 条件为j*j<=i
  • 难点三：状态转移方程

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

• 12.4
  1. dp[0]应该是0,因为凑整数0,需要0个数
  2. 填充函数忘了
  3. j=1;j*j<=i为第二层的结束条件(难点)

12
├─ 减 1² → 11
│   ├─ 减 1² → 10
│   │   ├─ 减 1² → 9 (1 step)
│   │   ├─ 减 4² ❌（超过）
│   │   └─ 减 9² → 1
│   └─ 减 4² → 7
│       └─ 减 4² → 3
└─ 减 4² → 8
    └─ 减 4² → 4
        └─ 减 4² → 0 ✅

+1 表示「在拼出前面的部分之后，又加上当前这个平方数」， 它是状态转移中“从旧状态走到新状态”的那一步。

• 事先填充
• i和j起点都为1

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        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];
    }
}