Week 45 @ 2024 算法周记【动态规划+回溯】
- Bryan
Owned by Bryan
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) 计算一个点右侧的最近蜡烛、左侧的最近蜡烛和两点之间的盘子数
动态规划
动态规划问题的一般形式就是求最值，求解动态规划的核心问题是穷举
写出暴力解
利用 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]
}迭代解法（进一步优化空间复杂度）
LC 322. 零钱兑换
https://leetcode.com/problems/coin-change
暴力解法（TLE）
动态规划
进一步优化常数时间（利用 MAX 代替 IntMax 来减少 if）
回溯
回溯算法和我们常说的 DFS 算法基本可以认为是同一种算法
抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
LC 46. Permutations 全排列
https://leetcode.com/problems/permutations
LC 51. N-Queens N 皇后
https://leetcode.com/problems/n-queens/