跳转至

LC279 - 完全平方数

PerfectSquares.go
 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
package DP

import "math"

func numSquares(n int) int {
    return numSquares2(n)
}

//func numSquares(n int) int {
//  // 1 <= n <= 10000
//  var f func(int, int) int
//  f = func(index, rest int) int {
//      if index == 0 {
//          if rest == 0 {
//              return 0
//          } else {
//              return math.MaxInt
//          }
//      }
//      cur := index * index
//      if rest < cur {
//          return f(index-1, rest)
//      } else {
//          return min(f(index, rest-cur)+1, f(index-1, rest))
//      }
//  }
//  return f(100, n)
//}

// 二维DP
// 时间复杂度: O(n * √n), 空间复杂度: O(n * √n)
func numSquares1(n int) int {
    // 1 <= n <= 10000
    // dp[i][j] -> dp[i-1][j], dp[i][j-x]
    dp := make([][]int, 101)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, n+1)
    }
    for j := 1; j <= n; j++ {
        dp[0][j] = math.MaxInt
    }
    for i := 1; i <= 100; i++ {
        for j := 1; j <= n; j++ {
            cur := i * i
            if j < cur {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = min(dp[i-1][j], dp[i][j-cur]+1)
            }
        }
    }
    return dp[100][n]
}

// 一维DP
// 时间复杂度: O(n * √n), 空间复杂度: O(n)
func numSquares2(n int) int {
    // dp[i] = min(dp[i], dp[i-j*j]+1)
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt
    }
    for i := 1; i <= n; i++ {
        for j := 1; j*j <= i; j++ {
            dp[i] = min(dp[i], dp[i-j*j]+1)
        }
    }
    return dp[n]
}

比较容易想到的方法是二维动态规划(numSquares1)，但最优解是一维动态规划(numSquares2)。