算法笔试-动态规划
Updated Time
|
2025-03-07 |
Category
|
|
Tags
|
关于语言：一刷用 Golang，二刷用 Rust
题单
多数题目会使用记忆化搜索和递推两种方式。
入门 dp
爬楼梯模型：
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 70. 爬楼梯 | 简单 | ||
| 746. 使用最小花费爬楼梯 | 第 63 场周赛 Q1 | 简单 | 1358 |
| 377. 组合总和 Ⅳ | 中等 | ||
| 2466. 统计构造好字符串的方案数 | 第 91 场双周赛 Q2 | 中等 | 1694 |
| 2266. 统计打字方案数 | 第 292 场周赛 Q3 | 中等 | 1857 |
打家劫舍模型，偷与不偷：
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 198. 打家劫舍 | 中等 | ||
| 740. 删除并获得点数 | 中等 | ||
| 2320. 统计放置房子的方式数 | 第 299 场周赛 Q2 | 中等 | 1608 |
| 213. 打家劫舍 II | 中等 |
双序列 dp：一般定义 \(dp[i][j]\) 表示对子问题 \((s1[:i],s2[:j])\) 的求解结果
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 1143. 最长公共子序列 | 中等 | ||
| 1092. 最短公共超序列 | 第 141 场周赛 Q4 | 困难 | 1977 |
| 72. 编辑距离 | 中等 |
题解
70. 爬楼梯
func climbStairs(n int) int {
memo := make([]int, n + 1)
var dfs func(int) int
dfs = func(x int) int {
if x <= 1 {
return 1
}
p := &memo[x]
if *p == 0 {
*p = dfs(x - 1) + dfs(x - 2)
}
return *p
}
return dfs(n)
}
func climbStairs(n int) int {
f := make([]int, n + 1)
f[0], f[1] = 1, 1
for i := 2; i <= n; i++ {
f[i] = f[i-1] + f[i-2]
}
return f[n]
}
746. 使用最小花费爬楼梯
func minCostClimbingStairs(cost []int) int {
n := len(cost)
memo := make([]int, n)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(x int) int {
if x < 0 {
return 0
}
p := &memo[x]
if *p < 0 {
*p = min(dfs(x - 1), dfs(x - 2)) + cost[x]
}
return *p
}
return min(dfs(n - 1), dfs(n - 2))
}
func minCostClimbingStairs(cost []int) int {
n := len(cost)
f := make([]int, n)
f[0], f[1] = cost[0], cost[1]
for i := 2; i < n; i++ {
f[i] = min(f[i-1], f[i-2]) + cost[i]
}
return min(f[n-1], f[n-2])
}
377. 组合总和 Ⅳ
func combinationSum4(nums []int, target int) int {
memo := make([]int, target + 1)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i <= 0 {
return 1
}
p := &memo[i]
if *p < 0 {
ans := 0
for _, x := range nums {
if x <= i {
ans += dfs(i - x)
}
}
*p = ans
}
return *p
}
return dfs(target)
}
func combinationSum4(nums []int, target int) int {
f := make([]int, target + 1)
f[0] = 1
for i := 1; i <= target; i++ {
for _, x := range nums {
if x <= i {
f[i] += f[i-x]
}
}
}
return f[target]
}
2466. 统计构造好字符串的方案数
func countGoodStrings(low int, high int, zero int, one int) int {
const mod int = 1e9 + 7
memo := make([]int, high + 1)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i < 0 {
return 0
}
if i == 0 {
return 1
}
p := &memo[i]
if *p < 0 {
*p = (dfs(i - zero) + dfs(i - one)) % mod
}
return *p
}
ans := 0
for i := low; i <= high; i++ {
ans += dfs(i)
}
return ans % mod
}
func countGoodStrings(low int, high int, zero int, one int) int {
const mod int = 1e9 + 7
f := make([]int, high + 11)
f[0] = 1
for i := 1; i <= high; i++ {
if i >= zero {
f[i] = (f[i] + f[i-zero]) % mod
}
if i >= one {
f[i] = (f[i] + f[i-one]) % mod
}
}
ans := 0
for i := low; i <= high; i++ {
ans += f[i]
}
return ans % mod
}
2266. 统计打字方案数
func countTexts(pressedKeys string) int {
const mod int = 1e9 + 7
n := len(pressedKeys)
memo := make([]int, n + 1)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i < 0 {
return 1
}
cnt, ans := 0, 0
if pressedKeys[i] == '7' || pressedKeys[i] == '9' {
cnt = 4
} else {
cnt = 3
}
p := &memo[i]
if *p < 0 {
for j := range cnt {
if i < j || pressedKeys[i-j] != pressedKeys[i] {
break
}
ans += dfs(i - j - 1)
}
*p = ans % mod
}
return *p
}
return dfs(n - 1) % mod
}
func countTexts(pressedKeys string) int {
const mod int = 1e9 + 7
n := len(pressedKeys)
f := make([]int, n + 1)
f[0] = 1
for i, v := range pressedKeys {
cnt := 0
if v == '7' || v == '9' {
cnt = 4
} else {
cnt = 3
}
for j := 0; j < cnt; j++ {
if i < j || pressedKeys[i-j] != pressedKeys[i] {
break
}
f[i+1] = (f[i+1] + f[i-j]) % mod
}
}
return f[n] % mod
}
198. 打家劫舍
func rob(nums []int) int {
n := len(nums)
memo := make([]int, n + 1)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i < 0 {
return 0
}
p := &memo[i]
if *p < 0 {
*p = max(dfs(i - 1) , dfs(i - 2) + nums[i])
}
return *p
}
return dfs(n - 1)
}
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
f := make([]int, n + 1)
f[0], f[1] = nums[0], max(nums[0], nums[1])
for i := 2; i < n; i++ {
f[i] = max(f[i-1], f[i-2] + nums[i])
}
return f[n-1]
}
740. 删除并获得点数
func deleteAndEarn(nums []int) int {
cnt := [10010]int{}
for _, v := range nums {
cnt[v] += v
}
slices.Sort(nums)
n := nums[len(nums)-1]
memo := make([]int, n + 1)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i < 0 {
return 0
}
p := &memo[i]
if *p < 0 {
*p = max(dfs(i - 1), dfs(i - 2) + cnt[i])
}
return *p
}
return dfs(n)
}
2320. 统计放置房子的方式数
func countHousePlacements(n int) int {
const mod int = 1e9 + 7
f := [10010]int{1, 2}
for i := 2; i <= n; i++ {
f[i] = (f[i-1] + f[i-2]) % mod
}
ans := (f[n] * f[n]) % mod
return ans
}
213. 打家劫舍 II
func rob1(nums []int, start, end int) int { // [start,end) 左闭右开
f0, f1 := 0, 0
for i := start; i < end; i++ {
f0, f1 = f1, max(f1, f0+nums[i])
}
return f1
}
func rob(nums []int) int {
n := len(nums)
return max(nums[0]+rob1(nums, 2, n-1), rob1(nums, 1, n))
}
1143. 最长公共子序列
\(f(i, j)\) 表示 \(text_1[0:i]\) 和 \(text_2[0:j]\) 的最长公共子序列长度。
func longestCommonSubsequence(text1 string, text2 string) int {
n, m := len(text1), len(text2)
f := make([][]int, n + 1)
for i := range f {
f[i] = make([]int, m + 1)
}
for i, t1 := range text1 {
for j, t2 := range text2 {
if t1 == t2 {
f[i+1][j+1] = f[i][j] + 1
} else {
f[i+1][j+1] = max(f[i][j+1], f[i+1][j])
}
}
}
return f[n][m]
}
72. 编辑距离
\(f(i, j-1)\) 相当于插入操作，\(f(i-1, j)\) 相当于删除 \(s\) 中的字符，\(f(i-1,j-1)\) 相当于替换操作。
func minDistance(word1 string, word2 string) int {
n, m := len(word1), len(word2)
f := make([][]int, n + 1)
for i := range f {
f[i] = make([]int, m + 1)
}
// 注意状态的初始化
for i := 1; i <= m; i++ {
f[0][i] = i
}
for i, w1 := range word1 {
f[i+1][0] = i + 1
for j, w2 := range word2 {
if w1 == w2 {
f[i+1][j+1] = f[i][j]
} else {
f[i+1][j+1] = min(min(f[i+1][j], f[i][j+1]), f[i][j]) + 1
}
}
}
return f[n][m]
}
1092. 最短公共超序列
func shortestCommonSupersequence(str1 string, str2 string) string {
n, m := len(str1), len(str2)
f := make([][]int, n + 1)
for i := range f {
f[i] = make([]int, m + 1)
f[i][0] = i
}
for j := 1; j <= m; j++ {
f[0][j] = j
}
for i, s1 := range str1 {
for j, s2 := range str2 {
f[i+1][j+1] = min(f[i+1][j], f[i][j+1]) + 1
if s1 == s2 {
f[i+1][j+1] = f[i][j] + 1
}
}
}
ans := []byte{}
i, j := n - 1, m - 1
for i >= 0 && j >= 0 {
if str1[i] == str2[j] {
ans = append(ans, str1[i])
i--
j--
} else if f[i+1][j+1] == f[i][j+1] + 1 {
ans = append(ans, str1[i])
i--
} else {
ans = append(ans, str2[j])
j--
}
}
slices.Reverse(ans)
return str1[:i+1] + str2[:j+1] + string(ans)
}