Leetcode-dynamic-programming

发表于 | 分类于 | |

1 DONE Min Cost Climbing Stairs

  • State "DONE" from "TODO" [2018-03-12 Mon 11:14] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func min(a, b int) int {
  if a > b {
    return b
  } else {
    return a
  }
}
func minCostClimbingStairs(cost []int) int {
  min_cost_arr := make([]int, len(cost))
  min_cost_arr[0] = cost[0]
  min_cost_arr[1] = cost[1]
  for index := 2; index < len(cost); index += 1 {
    min_cost_arr[index] = min(min_cost_arr[index-2],
      min_cost_arr[index-1])+cost[index]
  }

  return min(min_cost_arr[len(cost)-1], min_cost_arr[len(cost)-2])
}

2 DONE Climbing Stairs

  • State "DONE" from "TODO" [2018-03-12 Mon 11:26] 
1
2
3
4
5
6
7
8
9
10
11
12
13
func climbStairs(n int) int {
  if n < 3 {
    return n
  }
  s_ways := make([]int, n)
  s_ways[0] = 1
  s_ways[1] = 2
  for index := 2; index < n; index += 1 {
    s_ways[index] = s_ways[index-1] + s_ways[index-2]
  }

  return s_ways[n-1]
}

3 DONE House Robber

  • State "DONE" from "TODO" [2018-03-12 Mon 14:17] 
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
func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func rob(nums []int) int {
  if len(nums) < 1 {
    return 0
  }

  rob_nums := make([][]int, len(nums))
  for index, _ := range rob_nums {
    rob_nums[index] = make([]int, 2)
  }
  rob_nums[0][0] = nums[0]
  rob_nums[0][1] = 0
  for index := 1; index < len(nums); index += 1 {
    rob_nums[index][0] = rob_nums[index-1][1] + nums[index]
    rob_nums[index][1] = max(rob_nums[index-1][0], rob_nums[index-1][1])
  }

  return max(rob_nums[len(nums)-1][0], rob_nums[len(nums)-1][1])
}

4 DONE House Robber II

  • State "DONE" from "TODO" [2018-03-14 Wed 16:33] 
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
func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func robS(nums []int) int {
  if len(nums) < 1 {
    return 0
  }

  rob_nums := make([][]int, len(nums))
  for index, _ := range rob_nums {
    rob_nums[index] = make([]int, 2)
  }
  rob_nums[0][0] = nums[0]
  rob_nums[0][1] = 0
  for index := 1; index < len(nums); index += 1 {
    rob_nums[index][0] = rob_nums[index-1][1] + nums[index]
    rob_nums[index][1] = max(rob_nums[index-1][0], rob_nums[index-1][1])
  }

  return max(rob_nums[len(nums)-1][0], rob_nums[len(nums)-1][1])
}

func rob(nums []int) int {
  if len(nums) < 1 {
    return 0
  }

  if len(nums) == 1 {
    return nums[0]
  }

  return max(robS(nums[1:]), robS(nums[0:len(nums)-1]))
}

5 DONE Range Sum Query - Immutable

  • State "DONE" from "TODO" [2018-03-12 Mon 14:44] 
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
type NumArray struct {
  sums []int
}

func Constructor(nums []int) NumArray {
  if len(nums) < 2 {
    return NumArray{
      sums: nums,
    }
  }

  sums := make([]int, len(nums))
  sums[0] = nums[0]
  for index := 1; index < len(nums); index += 1 {
    sums[index] = sums[index-1] + nums[index]
  }

  return NumArray{
    sums: sums,
  }
}

func (this *NumArray) SumRange(i int, j int) int {
  if len(this.sums) < 1 {
    return 0
  }
  if i == 0 {
    return this.sums[j]
  } else {
    return this.sums[j] - this.sums[i-1]
  }
}

6 DONE Counting Bits

  • State "DONE" from "TODO" [2018-03-12 Mon 16:22] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func countBits(num int) []int {
  if num < 1 {
    return []int{0}
  }

  if num == 1 {
    return []int{0, 1}
  }

  bit_nums := make([]int, 0)
  bit_nums[0] = 0
  bit_nums[1] = 1
  index := 1
  for index < num {
    index *= 2
    bit_nums[index] = 1
    for i := 1; i < index && i+index <= num; i += 1 {
      bit_nums[index+i] = 1 + bit_nums[i]
    }
  }

  return bit_nums
}

7 DONE Palindromic Substrings

  • State "DONE" from "TODO" [2018-03-12 Mon 18:20] 
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
func countSubstrings(s string) int {
  if len(s) < 1 {
    return 0
  }
  subStrs := make([]int, len(s))
  subStrs[0] = 1
  for i := 1; i < len(s); i += 1 {
    subStrs[i] = subStrs[i-1] + 1
    for j := i - 1; j >= 0; j -= 1 {
      if isPalindromic(s[j : i+1]) {
	subStrs[i] += 1
      }
    }
  }

  return subStrs[len(s)-1]
}

func isPalindromic(s string) bool {
  for i := 0; i < len(s)/2; i += 1 {
    if s[i] != s[len(s)-1-i] {
      return false
    }
  }

  return true
}

8 DONE Minimum ASCII Delete Sum for Two Strings

  • State "DONE" from "TODO" [2018-03-13 Tue 22:04] 
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
func min(a, b int) int {
  if a > b {
    return b
  } else {
    return a
  }
}
func minimumDeleteSum(s1 string, s2 string) int {
  dps := make([][]int, len(s1)+1)
  for i, _ := range dps {
    dps[i] = make([]int, len(s2)+1)
  }

  for i := len(s1) - 1; i >= 0; i -= 1 {
    dps[i][len(s2)] = dps[i+1][len(s2)] + int(s1[i])
  }

  for i := len(s2) - 1; i >= 0; i -= 1 {
    dps[len(s1)][i] = dps[len(s1)][i+1] + int(s2[i])
  }

  for i := len(s1) - 1; i >= 0; i -= 1 {
    for j := len(s2) - 1; j >= 0; j -= 1 {
      if s1[i] == s2[j] {
	dps[i][j] = dps[i+1][j+1]
      } else {
	dps[i][j] = min(
	  dps[i+1][j]+int(s1[i]),
	  dps[i][j+1]+int(s2[j]))
      }
    }
  }

  return dps[0][0]
}

9 DONE Arithmetic Slices

  • State "DONE" from "TODO" [2018-03-12 Mon 17:31] 
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
type ASStatus struct {
  Num      int
  InAs     bool
  SizeOfAs int
  DiffNum  int
}

func numberOfArithmeticSlices(A []int) int {
  if len(A) < 3 {
    return 0
  }

  ass_arr := make([]*ASStatus, len(A))
  ass_arr[0] = &ASStatus{}
  ass_arr[1] = &ASStatus{}
  for i := 2; i < len(A); i += 1 {
    if ass_arr[i-1].InAs {
      if A[i]-A[i-1] == ass_arr[i-1].DiffNum {
	ass_arr[i] = &ASStatus{
	  Num:      ass_arr[i-1].Num + ass_arr[i-1].SizeOfAs - 1,
	  InAs:     true,
	  SizeOfAs: ass_arr[i-1].SizeOfAs + 1,
	  DiffNum:  ass_arr[i-1].DiffNum,
	}
      } else {
	ass_arr[i] = &ASStatus{
	  Num: ass_arr[i-1].Num,
	}
      }
    } else {
      if A[i]-A[i-1] == A[i-1]-A[i-2] {
	ass_arr[i] = &ASStatus{
	  Num:      ass_arr[i-1].Num + 1,
	  InAs:     true,
	  SizeOfAs: 3,
	  DiffNum:  A[i] - A[i-1],
	}
      } else {
	ass_arr[i] = &ASStatus{
	  Num: ass_arr[i-1].Num,
	}
      }
    }
  }

  return ass_arr[len(A)-1].Num
}
1
2
3
4
5
6
7
8
9
10
11
12
func numberOfArithmeticSlices(A []int) int {
  dp := make([]int, len(A))
  var sum int
  for i = 2; i < len(A); i += 1 {
    if A[i]-A[i-1] == A[i-1]-A[i-2] {
      dp[i] = 1 + dp[i-1]
      sum += dp[i]
    }
  }

  return sum
}

10 TODO Arithmetic Slices II - Subsequence

1
2
func numberOfArithmeticSlices(A []int) int {
}

11 DONE Maximum Length of Pair Chain

  • State "DONE" from "TODO" [2018-03-12 Mon 23:01] 
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
import "sort"

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}
func findLongestChain(pairs [][]int) int {
  if len(pairs) < 2 {
    return len(pairs)
  }

  sort.Slice(
    pairs,
    func(i, j int) bool {
      return pairs[i][0] < pairs[j][0]
    })
  dps := make([]int, len(pairs))
  for i, _ := range dps {
    dps[i] = 1
  }

  for i := 1; i < len(pairs); i += 1 {
    for j := 0; j < i; j += 1 {
      if pairs[j][1] < pairs[i][0] {
	dps[i] = max(dps[j]+1, dps[i])
      }
    }
  }

  mx := 0
  for _, dp := range dps {
    if dp > mx {
      mx = dp
    }
  }

  return mx
}

12 DONE Integer Break

  • State "DONE" from "TODO" [2018-03-13 Tue 12:00] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func integerBreak(n int) int {
  if n < 3 {
    return 1
  }

  if n == 3 {
    return 2
  }

  k := math.Floor(float64(n) / 3.0)
  r = n % 3
  if r == 0 {
    return int(math.Pow(3.0, k))
  } else if r == 1 {
    return 4 * int(math.Pow(3.0, k-1))
  } else {
    return 2 * int(math.Pow(3.0, k))
  }
}

13 DONE LCS

  • State "DONE" from "TODO" [2018-03-13 Tue 18:32] 
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
func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func LCS(lstr, rstr string) string {
  dps := make([][]int, len(lstr)+1)
  for i, _ := range dps {
    dps[i] = make([]int, len(rstr)+1)
  }

  for i := 1; i <= len(lstr); i += 1 {
    for j := 1; j <= len(rstr); j += 1 {
      if lstr[i-1] == rstr[j-1] {
	dps[i][j] = dps[i-1][j-1] + 1
      } else {
	dps[i][j] = max(dps[i-1][j], dps[i][j-1])
      }
    }
  }

  byteLCS := make([]byte, dps[len(lstr)][len(rstr)])
  i := len(lstr)
  j := len(rstr)
  for i > 0 && j > 0 {
    if lstr[i-1] == rstr[j-1] {
      byteLCS[dps[i][j]-1] = lstr[i-1]
      i -= 1
      j -= 1
    } else if dps[i-1][j] > dps[i][j-1] {
      i -= 1
    } else {
      j -= 1
    }
  }

  return string(byteLCS)
}
"main no"body

14 DONE Count Numbers with Unique Digits

  • State "DONE" from "TODO" [2018-03-13 Tue 23:10] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func countNumbersWithUniqueDigits(n int) int {
  if n == 0 {
    return 1
  }

  dps := make([]int, n+1)
  dps[0] = 1
  dps[1] = 9
  for i := 2; i <= n; i += 1 {
    if i > 9 {
      dps[i] = 0
    } else {
      dps[i] = dps[i-1] * (11 - i)
    }
  }

  c := 0
  for _, dp := range dps {
    c += dp
  }

  return c
}

15 DONE Longest Increasing Subsequence

  • State "DONE" from "TODO" [2018-03-14 Wed 11:43] 
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
func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func lengthOfLIS(nums []int) int {
  if len(nums) < 1 {
    return 0
  }

  dp := make([]int, len(nums))
  dp[0] = 1
  maxAns := 1
  for i := 1; i < len(nums); i += 1 {
    var maxVal int
    for j := 0; j < i; j += 1 {
      if nums[i] > nums[j] {
	maxVal = max(maxVal, dp[j])
      }
    }
    dp[i] = maxVal + 1
    maxAns = max(maxAns, dp[i])
  }

  return maxAns
}

16 DONE Number of Longest Increasing Subsequence

  • State "DONE" from "TODO" [2018-03-14 Wed 12:05] 
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
func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func findNumberOfLIS(nums []int) int {
  if len(nums) < 2 {
    return len(nums)
  }

  lengths := make([]int, len(nums))
  counts := make([]int, len(nums))
  for i, _ := range counts {
    counts[i] = 1
  }

  lengths[0] = 1
  maxAns := 1
  for i := 1; i < len(nums); i += 1 {
    var maxVal int
    for j := 0; j < i; j += 1 {
      if nums[i] > nums[j] {
	if lengths[j] > maxVal {
	  counts[i] = counts[j]
	  maxVal = lengths[j]
	} else if lengths[j] == maxVal {
	  counts[i] += counts[j]
	}
      }
    }
    lengths[i] = maxVal + 1
    maxAns = max(maxAns, lengths[i])
  }

  var sum int
  for i, _ := range lengths {
    if lengths[i] == maxAns {
      sum += counts[i]
    }
  }

  return sum
}

17 DONE Longest Palindromic Substring

  • State "DONE" from "TODO" [2018-03-14 Wed 15:51] 
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
package main

import "fmt"

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func longestPalindrome(s string) string {
  var start, end int
  for i := 0; i < len(s); i += 1 {
    length_s := expandAroundCenter(s, i, i)
    length_d := expandAroundCenter(s, i, i+1)
    length := max(length_s, length_d)
    if length > end-start {
      start = i - (length-1)/2
      end = i + length/2
    }
  }

  return s[start : end+1]
}

func expandAroundCenter(s string, left, right int) int {
  l, r := left, right
  for l >= 0 && r < len(s) && s[l] == s[r] {
    l -= 1
    r += 1
  }

  return r - l - 1
}

func main() {
  fmt.Println(longestPalindrome("abacdfgdcaba"))
}

18 DONE Longest Palindromic Subsequence

  • State "DONE" from "TODO" [2018-03-14 Wed 16:01] 
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
func reverse(s string) string {
  r := []rune(s)
  for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
    r[i], r[j] = r[j], r[i]
  }
  return string(r)
}

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func lengthOfLCS(lstr, rstr string) int {
  dps := make([][]int, len(lstr)+1)
  for i, _ := range dps {
    dps[i] = make([]int, len(rstr)+1)
  }

  for i := 1; i <= len(lstr); i += 1 {
    for j := 1; j <= len(rstr); j += 1 {
      if lstr[i-1] == rstr[j-1] {
	dps[i][j] = dps[i-1][j-1] + 1
      } else {
	dps[i][j] = max(dps[i-1][j], dps[i][j-1])
      }
    }
  }

  return dps[len(lstr)][len(rstr)]
}

func longestPalindromeSubseq(s string) int {
  return lengthOfLCS(s, reverse(s))
}

19 WAITING Predict the Winner

  • State "WAITING" from "TODO" [2018-03-14 Wed 18:05]
    minimax算法学习 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func PredictTheWinner(nums []int) bool {
  return winner(nums, 1) >= 0
}

func winner(nums []int, turn int) int {
  if len(nums) == 1 {
    return turn * nums[0]
  }

  s := turn*nums[0] + winner(nums[1:], -turn)
  e := turn*nums[len(nums)-1] + winner(nums[0:len(nums)-2], -turn)

  return turn * max(turn*s, turn*e)
}

20 DONE Best Time to Buy and Sell Stock with Cooldown

  • State "DONE" from "TODO" [2018-03-15 Thu 18:25] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func maxProfit(prices []int) int {
  if len(prices) < 2 {
    return 0
  }

  sell, buy, prev_sell, prev_buy = 0, -prices[0], 0, 0
  for _, price := range prices {
    prev_buy = buy
    buy = max(prev_sell-price, prev_buy)
    prev_sell = sell
    sell = max(prev_buy+price, prev_sell)
  }

  return sell
}

21 DONE Best Time to Buy and Sell Stock with Transaction Fee

  • State "DONE" from "TODO" [2018-03-15 Thu 17:14] 
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
package main

import "fmt"

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func maxProfit(prices []int, fee int) int {
  if len(prices) < 2 {
    return 0
  }

  cash, hold := 0, -prices[0]
  for i := 1; i < len(prices); i += 1 {
    cash = max(cash, hold+prices[i]-fee)
    hold = max(hold, cash-prices[i])
  }

  return cash
}

func main() {
  fmt.Println(maxProfit([]int{1, 3, 2, 5, 8, 4, 9, 3}, 2))
}

22 DONE Is Subsequence

  • State "DONE" from "TODO" [2018-03-14 Wed 18:19] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func isSubsequence(s string, t string) bool {
  if len(s) < 1 {
    return true
  }

  if len(s) > len(t) {
    return false
  }

  s_i := 0
  for t_i, _ := range t {
    if t[t_i] == s[s_i] {
      s_i += 1
    }
    if s_i == len(s) {
      break
    }
  }

  return s_i == len(s)
}

23 WAITING Knapsack problem（背包问题）

  • State "WAITING" from "TODO" [2018-03-15 Thu 15:12]
    背包算法，需要好好研究 
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
package main

import "fmt"

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func knap(weights []int, values []int, capacity int) int {
  dps := make([][]int, len(weights)+1)
  for i, _ := range dps {
    dps[i] = make([]int, capacity+1)
  }

  for i := 1; i < len(weights)+1; i += 1 {
    for j := 0; j <= capacity; j += 1 {
      if j < weights[i-1] {
	dps[i][j] = dps[i-1][j]
      } else {
	dps[i][j] = max(dps[i-1][j], dps[i-1][j-weights[i-1]]+values[i-1])
      }
    }
  }

  for _, dp := range dps {
    fmt.Println(dp)
  }

  return dps[len(weights)][capacity]
}

func main() {
  fmt.Println(knap([]int{5, 4, 7, 2, 6}, []int{12, 3, 10, 3, 6}, 15))
}
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
package main

import "fmt"

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func knap(weights []int, values []int, capacity int) int {
  dp := make([]int, capacity+1)

  for i := 1; i < len(weights)+1; i += 1 {
    for j := capacity; j >= weights[i-1]; j -= 1 {
      dp[j] = max(dp[j], dp[j-weights[i-1]]+values[i-1])
    }
    fmt.Println(dp)
  }

  return dp[capacity]
}

func main() {
  fmt.Println(knap([]int{5, 4, 7, 2, 6}, []int{12, 3, 10, 3, 6}, 15))
}
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
package main

import "fmt"

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func knap(weights []int, values []int, capacity int) int {
  dp := make([]int, capacity+1)
  for i := 1; i <= capacity; i += 1 {
    dp[i] = -10000
  }

  for i := 1; i < len(weights)+1; i += 1 {
    for j := capacity; j >= weights[i-1]; j -= 1 {
      dp[j] = max(dp[j], dp[j-weights[i-1]]+values[i-1])
    }
    fmt.Println(dp)
  }

  return dp[capacity]
}

func main() {
  fmt.Println(knap([]int{5, 4, 7, 2, 6}, []int{12, 3, 10, 3, 6}, 15))
}

24 DONE Maximum Length of Repeated Subarray

  • State "DONE" from "TODO" [2018-03-16 Fri 11:00] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func findLength(A []int, B []int) int {
  dps := make([][]int, len(A)+1)
  for i, _ := range dps {
    dps[i] = make([]int, len(B)+1)
  }

  maxAns := 0
  for i := 1; i <= len(A); i += 1 {
    for j := 1; j <= len(B); j += 1 {
      if A[i-1] == B[j-1] {
	dps[i][j] = dps[i-1][j-1] + 1
      } else {
	dps[i][j] = 0
      }

      if dps[i][j] > maxAns {
	maxAns = dps[i][j]
      }
    }
  }

  return maxAns
}

25 DONE Coin Change

  • State "DONE" from "TODO" [2018-03-16 Fri 15:20] 
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
func coinChange(coins []int, amount int) int {
  if len(coins) < 1 {
    return -1
  }
  if amount == 0 {
    return 0
  }

  dp := make([]int, amount+1)
  for i, _ := range dp {
    dp[i] = -1
  }

  sort.Ints(coins)
  for _, coin := range coins {
    if coin <= amount {
      dp[coin] = 1
    }
  }

  for i := 1; i <= amount; i += 1 {
    if dp[i] == 1 {
      continue
    }

    for j := len(coins) - 1; j >= 0; j -= 1 {
      coin := coins[j]
      if coin > i {
	continue
      }

      if dp[i-coin] > 0 {
	if dp[i] == -1 || dp[i] > dp[i-coin]+dp[coin] {
	  dp[i] = dp[i-coin] + dp[coin]
	}
      }
    }
  }

  return dp[amount]
}

26 DONE 2 Keys Keyboard

  • State "DONE" from "TODO" [2018-03-16 Fri 17:54] 
1
2
3
4
5
6
7
8
9
10
11
12
func minSteps(n int) int {
  ans, d := 0, 2
  for n > 1 {
    for n%d == 0 {
      ans += d
      n /= d
    }
    d += 1
  }

  return ans
}

27 DONE Shopping Offers

  • State "DONE" from "TODO" [2018-03-16 Fri 18:20] 
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
func shoppingOffers(price []int, special [][]int, needs []int) int {
  var ans int
  for i := 0; i < len(price); i += 1 {
    ans += price[i] * needs[i]
  }

  for i := 0; i < len(special); i += 1 {
    c_needs := make([]int, len(needs))
    copy(c_needs, needs)
    j := 0
    for j = 0; j < len(needs); j += 1 {
      rest := needs[j] - special[i][j]
      if rest < 0 {
	break
      }
      c_needs[j] = rest
    }

    if j == len(needs) {
      ans = min(ans, c_needs[i][j]+shoppingOffers(price, special, c_needs))
    }
  }

  return ans
}

func min(a, b int) int {
  if a > b {
    return b
  } else {
    return a
  }
}
Last Updated 2018-04-25 Wed 22:17.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)