Leetcode 279:完全平方数即类似题（动态规划求最小值或最大值）

来源

动态规划

对于数n，n=m*m+(n-m*m), f(n)表示和为n的完全平方数的最少数量，则f(n) =1+f(n-m*m)

建立一个长度为n+1的表，记录每一个f(i)

$i = {j^2} + (i - {j^2})$,其中$j <  = \sqrt i $

$f(i) = 1 + f(i - {j^2})$

$\min f(i) = 1 + \min f(i - {j^2})$

 1 class Solution {
 2     public int numSquares(int n) {
 3         int[] f = new int[n+1]; //f[i]表示
 4         f[0] = 0;
 5 
 6         //填表f
 7         for(int i = 1; i){
 8             //对于每一个f[i]
 9             int minn = Integer.MAX_VALUE;
10             for(int j = 1; j*j <= i; j++){
11                 minn = Math.min(minn, f[i-j*j]);
12             }
13             f[i] = minn + 1;
14         }
15         return f[n];
16     }
17 }

类似题：

300：最长递增子序列

322:零钱兑换