8000 update a solution · AlgoBBA/awesome-golang-algorithm@e9a6c3b · GitHub
[go: up one dir, main page]
Skip to content

Commit e9a6c3b

Browse files
author
Kyle Liu
committed
update a solution
1 parent 07941ae commit e9a6c3b

File tree

3 files changed

+57
-1
lines changed

3 files changed

+57
-1
lines changed

‎lcof/of037/Solution_test.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,6 @@ func TestSolution(t *testing.T) {
1212
//ser := Constructor();
1313
deser := Constructor()
1414
//data := ser.serialize(root);
15-
ans := deser.deserialize("1")
15+
ans := deser.deserialize("1,nil,nil")
1616
fmt.Println(ans)
1717
}

‎leetcode/301-400/0322.Coin-Change/Solution.go

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package Solution
22

3+
import "math"
4+
35
func coinChange(coins []int, amount int) int {
46
dp := make([]int, amount+1)
57
for i := 0; i < amount+1; i++ {
@@ -11,6 +13,7 @@ func coinChange(coins []int, amount int) int {
1113
for j := 0; j < len(coins); j++ {
1214
if coins[j] <= i {
1315
dp[i] = min(dp[i], dp[i-coins[j]]+1)
16+
1417
}
1518
}
1619
}
@@ -26,3 +29,54 @@ func min(x, y int) int {
2629
}
2730
return x
2831
}
32+
33+
//动态规划（不压缩空间）
34+
func coinChange2(coins []int, amount int) int {
35+
dp := make([][]int, len(coins)+1) //定义状态
36+
for i := 0; i <= len(coins); i++ {
37+
dp[i] = make([]int, amount+1)
38+
}
39+
//初始条件
40+
for j := 0; j <= amount; j++ {
41+
dp[0][j] = amount + 1
42+
}
43+
dp[0][0] = 0
44+
for i := 1; i <= len(coins); i++ {
45+
for j := 0; j <= amount; j++ {
46+
//状态转移方程
47+
if j >= coins[i-1] {
48+
dp[i][j] = int(math.Min(float64(dp[i-1][j]), float64(dp[i][j-coins[i-1]]+1)))
49+
} else {
50+
dp[i][j] = dp[i-1][j]
51+
}
52+
}
53+
}
54+
if dp[len(coins)][amount] > amount {
55+
return -1
56+
} else {
57+
return dp[len(coins)][amount]
58+
}
59+
}
60+
61+
//动态规划（压缩空间）
62+
func coinChange3(coins []int, amount int) int {
63+
dp := make([]int, amount+1)
64+
//初始值
65+
for i := 0; i <= amount; i++ {
66+
dp[i] = amount + 1
67+
}
68+
dp[0] = 0
69+
70+
for i := 1; i <= len(coins); i++ {
71+
for j := 0; j <= amount; j++ {
72+
if j >= coins[i-1] {
73+
dp[j] = int(math.Min(float64(dp[j]), float64(dp[j-coins[i-1]]+1)))
74+
}
75+
}
76+
}
77+
if dp[amount] > amount {
78+
return -1
79+
} else {
80+
return dp[amount]
81+
}
82+
}

‎leetcode/301-400/0322.Coin-Change/Solution_test.go

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,8 @@ type SolutionFuncType func([]int, int) int
1212

1313
var SolutionFuncList = []SolutionFuncType{
1414
coinChange,
15+
coinChange2,
16+
coinChange3,
1517
}
1618

1719
// test info struct

0 commit comments

Comments
 (0)
0