1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76  // @Title: 完全平方数 (Perfect Squares) // @Author: 15816537946@163.com // @Date: 2019-11-19 00:38:27 // @Runtime: 36 ms // @Memory: 5.6 MB /* * @lc app=leetcode.cn id=279 lang=golang * * [279] 完全平方数 * * https://leetcode-cn.com/problems/perfect-squares/description/ * * algorithms * Medium (50.98%) * Likes: 180 * Dislikes: 0 * Total Accepted: 18.2K * Total Submissions: 35.8K * Testcase Example: '12' * * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 * * 示例 1: * * 输入: n = 12 * 输出: 3 * 解释: 12 = 4 + 4 + 4. * * 示例 2: * * 输入: n = 13 * 输出: 2 * 解释: 13 = 4 + 9. * */ /* func numSquares(n int) int { dp := make([]int,n+1) // dp[0] = 0 for i :=1;i=0;j++ { dp[i] = min(dp[i], dp[i-j*j]+1) } } return dp[n] } func min(a,b int) int { if a > b { return b } return a } */ func numSquares(n int) int { dp := make([]int, n+1) for i := 1; i < n+1; i++ { dp[i] = i for j := 1; i-j*j >= 0; j++ { dp[i] = min(dp[i], dp[i-j*j]+1) } } return dp[n] } func min(a, b int) int { if a > b { return b } return a }