题目链接

完全平方数

题目描述

image.png

实现代码

动态规划思想：

  1. class Solution {
  2.     public int numSquares(int n) {
  4.         if(n == 1) {
  5.             return 1;
  6.         }
  7.         int[] dp = new int[n+1];
  8.         dp[1] = 1;
  9.         int result = Integer.MAX_VALUE;
  10.         for(int i=2; i<=n; i++) {
  11.             int min = Integer.MAX_VALUE;
  12.             for(int j=1; j*j <= i; j++) {
  13.                 min = Math.min(min, dp[i-j*j] + 1);
  14.             }
  15.             dp[i] = min;
  16.             if(i == n) {
  17.                 result = Math.min(result, min);
  18.             }
  19.         }
  22.         return result;
  23.     }
  24. }