Week 45 @ 2024 算法周记【动态规划+回溯】

By Bryan
4 min

LC 2055. Plates Between Candles 蜡烛之间的盘子

https://leetcode.com/problems/plates-between-candles/

func platesBetweenCandles(s string, queries [][]int) []int { plates := make([]int, len(s)) candelsL := make([]int, len(s)) candelsR := make([]int, len(s)) candelsR[0] = -1 for i := 1; i < len(s); i++ { if s[i] == '|' { // candel plates[i] = plates[i-1] candelsR[i] = i } else { // plate plates[i] = plates[i-1] + 1 candelsR[i] = candelsR[i-1] } } candelsL[len(s)-1] = -1 for i := len(s)-2; i >= 0; i-- { if s[i] == '|' { // candel candelsL[i] = i } else { // plate candelsL[i] = candelsL[i+1] } } result := make([]int, len(queries)) for i, q := range queries { L := candelsL[q[0]] R := candelsR[q[1]] if L == -1 || R == -1 || L >= R { result[i] = 0 } else { result[i] = plates[R] - plates[L] } } return result }

预处理前缀和，做到 O(1) 计算一个点右侧的最近蜡烛、左侧的最近蜡烛和两点之间的盘子数

动态规划

动态规划问题的一般形式就是求最值，求解动态规划的核心问题是穷举

  1. 写出暴力解

  2. 利用 memory table / 数组优化暴力解

LC 509. Fibonacci Number 斐波那契数

https://leetcode.com/problems/fibonacci-number

递归解法

func fib(n int) int { if n == 0 || n == 1 { return n } return fib(n - 1) + fib(n - 2) }

迭代解法

func fib(n int) int { if n == 0 || n == 1 { return n } dp := make([]int, n + 1) dp[1] = 1 for i := 2; i <= n; i++ { dp[i] = dp[i-1] + dp[i-2] } return dp[n] }

迭代解法（进一步优化空间复杂度）

func fib(n int) int { if n == 0 || n == 1 { return n } a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a + b } return b }

LC 322. 零钱兑换

https://leetcode.com/problems/coin-change

暴力解法（TLE）

func coinChange(coins []int, amount int) int { t := change(coins, amount, 0) if t == math.MaxInt { return -1 } return t } func change(coins []int, amount int, currentTimes int) int { if amount == 0 { return currentTimes } minTimes := math.MaxInt for _, coin := range coins { balance := amount - coin if balance >= 0 { minTimes = min(minTimes, change(coins, balance, currentTimes + 1)) } } return minTimes }

动态规划

func coinChange(coins []int, amount int) int { dp := make([]int, amount + 1) for x := 1; x <= amount; x++ { minTimes := math.MaxInt for _, coin := range coins { balance := x - coin if balance >= 0 && dp[balance] >= 0 { minTimes = min(minTimes, dp[balance] + 1) } } if minTimes == math.MaxInt { dp[x] = -1 } else { dp[x] = minTimes } } // fmt.Println(dp) return dp[amount] }

进一步优化常数时间（利用 MAX 代替 IntMax 来减少 if）

func coinChange(coins []int, amount int) int { MAX := amount+1 dp := make([]int, amount + 1) for x := 1; x <= amount; x++ { dp[x] = MAX for _, coin := range coins { balance := x - coin if balance >= 0 { dp[x] = min(dp[x], dp[balance] + 1) } } } if dp[amount] >= MAX { return -1 } return dp[amount] }

回溯

回溯算法和我们常说的 DFS 算法基本可以认为是同一种算法

抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

LC 46. Permutations 全排列

https://leetcode.com/problems/permutations

func permute(nums []int) (result [][]int) { backtrack(&result, nums, make([]int, 0, len(nums)), make(map[int]bool, len(nums))) return } func backtrack(result *[][]int, nums []int, current []int, used map[int]bool) { if len(current) == len(nums) { *result = append(*result, append([]int(nil), current...)) return } for _, num := range nums { if used[num] { continue } current = append(current, num) used[num] = true backtrack(result, nums, current, used) current = current[:len(current)-1] used[num] = false } }

LC 51. N-Queens N 皇后

https://leetcode.com/problems/n-queens/

func solveNQueens(n int) (result [][]string) { solve(&result, n, newBoard(n), 0) return } func solve(result *[][]string, n int, board [][]byte, row int) { if row == n { *result = append(*result, flat(board)) return } for col := 0; col < n; col++ { if !isValid(board, row, col) { continue } board[row][col] = 'Q' solve(result, n, board, row+1) board[row][col] = '.' } } func isValid(board [][]byte, row, col int) bool { n := len(board) for i := 0; i <= row; i++ { if board[i][col] == 'Q' { return false } } for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 { if board[i][j] == 'Q' { return false } } for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 { if board[i][j] == 'Q' { return false } } return true } func newBoard(n int) [][]byte { board := make([][]byte, n) for i := range board { board[i] = bytes.Repeat([]byte("."), n) } return board } func flat(board [][]byte) []string { result := make([]string, len(board)) for i := range result { result[i] = string(board[i]) } return result }

LC 52. N-Queens II N 皇后 II

https://leetcode.com/problems/n-queens-ii/

func totalNQueens(n int) (result int) { solve(&result, n, newBoard(n), 0) return } func solve(result *int, n int, board [][]byte, row int) { if row == n { (*result)++ return } for col := 0; col < n; col++ { if !isValid(board, row, col) { continue } board[row][col] = 'Q' solve(result, n, board, row+1) board[row][col] = '.' } } func isValid(board [][]byte, row, col int) bool { n := len(board) for i := 0; i <= row; i++ { if board[i][col] == 'Q' { return false } } for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 { if board[i][j] == 'Q' { return false } } for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 { if board[i][j] == 'Q' { return false } } return true } func newBoard(n int) [][]byte { board := make([][]byte, n) for i := range board { board[i] = bytes.Repeat([]byte("."), n) } return board }

Related content