DAY 38

斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
func fib(n int) int {
if n == 0 || n == 1 {
return n
}

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

爬楼梯

1
2
3
4
5
6
7
8
9
10
11
func climbStairs(n int) int {
if n == 1 {
return 1
}
dp := make([]int, n+1)
dp[0], dp[1] = 1, 1
for i := 2; i <= n; i++ {
dp[i] += dp[i-1] + dp[i-2]
}
return dp[n]
}

使用最小花费爬楼梯

1
2
3
4
5
6
7
8
func minCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n+1)
for i := 2; i <= n; i++ {
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}

DAY 39

不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
for i := 0; i < m; i++ {
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}

不同路径 II

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
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m, n := len(obstacleGrid), len(obstacleGrid[0])
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
for i := 0; i < m; i++ {
if obstacleGrid[i][0] == 1 {
break
}
dp[i][0] = 1
}
for j := 0; j < n; j++ {
if obstacleGrid[0][j] == 1 {
break
}
dp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] == 1 {
continue
}
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}

DAY 40

周日休息

DAY 41

整数拆分

定义 dp[i] 为拆分 i 的最大乘积,我们最后要求到 dp[n]

递推公式:dp[i]=max(dp[i],j*(i-j),j*dp[i-j])

1
2
3
4
5
6
7
8
9
10
func integerBreak(n int) int {
dp := make([]int, n+1)
dp[1], dp[2] = 1, 1
for i := 3; i <= n; i++ {
for j := 1; j < i+1; j++ {
dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]))
}
}
return dp[n]
}

不同的二叉搜索树

卡特兰数,dp[i]=sum(dp[j-1]*dp[i-j])

1
2
3
4
5
6
7
8
9
10
func numTrees(n int) int {
dp := make([]int, n+1)
dp[0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
dp[i] += dp[j-1] * dp[i-j]
}
}
return dp[n]
}

DAY 42(背包问题)

朴素 01 背包

假设你有 N 个物品,每个物品有一个重量 w[i] 和一个价值 v[i]。同时你有一个容量为 W 的背包。目标是在不超过背包容量的情况下,最大化装入背包的物品总价值

dp[i][j] 表示前 i 件物品(部分或全部)放入一个容量为 j 的背包可以获得的最大价值

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
func knapsack(weight, value []int, W, N int) int {
dp := make([][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([]int, W+1)
}

// 二维 dp 需要把第 0 件物品先初始化
for j := 0; j <= W; j++ {
if j >= weight[0] {
dp[0][j] = value[0]
}
}

for i := 1; i < N; i++ { // 剩下的物品
for j := 0; j <= W; j++ { // 背包 0...W
if j < weight[i] { // 如果放不下
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
}
}
}

return dp[N-1][W]
}

滚动数组 01 背包

因为每次状态转移只依赖上一次的状态,所以可以使用滚动数组压缩到一维

记住这个一维的就好了,而且记住背包是逆序遍历,如果是正序就是完全背包了

1
2
3
4
5
6
7
8
9
func knapsack(weight, value []int, W, N int) int {
dp := make([]int, W+1)
for i := 0; i < N; i++ { // 所有物品
for j := W; j >= weight[i]; j-- { // 背包 W...weight[i]
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}
return dp[W]
}

变体之「恰好装满」

如果要求「恰好装满」则可以这样处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   func knapsackExact(weight, value []int, W, N int) int {
dp := make([]int, W+1)
+ for i := 1; i <= W; i++ { // 将 1...W 初始化为 -INF
+ dp[i] = math.MinInt
+ }
for i := 0; i < N; i++ { // 所有物品
for j := W; j >= weight[i]; j-- { // 背包 W...weight[i]
+ if dp[j-weight[i]] != math.MinInt { // 越界检查,仅处理正常值
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
+ }
}
}
return dp[W] // 如果还是 -INF 则没法恰好装满
}

变体之「恰好装满方案个数」

这时 dp[i] 的含义就变成方案个数了,并且转移方程也变了,但是要牢记不变的遍历顺序

1
2
3
4
5
6
7
8
9
10
11
  func knapsackExactCount(weight []int, W, N int) int {
dp := make([]int, W+1)
+ dp[0] = 1 // 无物品时,恰好装满重量为0的方式有一种
for i := 0; i < N; i++ { // 所有物品
for j := W; j >= weight[i]; j-- { // 背包 W...weight[i]
- dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
+ dp[j] += dp[j-weight[i]]
}
}
return dp[W] // 返回恰好装满背包的方案数
}

变体之「多维背包」

假如物品不止重量一个限制条件,而是还有体积等其他维度条件,则为多维背包问题

每多一个维度就加一维 dpfor 就行,下面以二维举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  func knapsack2D(weight, volume, value []int, W, V, N int) int {
- dp := make([]int, W+1)
+ dp := make([][]int, W+1)
+ for i := range dp {
+ dp[i] = make([]int, V+1)
+ }
+
for i := 0; i < N; i++ { // 所有物品
for j := W; j >= weight[i]; j-- { // 背包重量 W...weight[i]
+ for k := V; k >= volume[i]; k-- { // 背包体积 V...volume[i]
- dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
+ dp[j][k] = max(dp[j][k], dp[j-weight[i]][k-volume[i]]+value[i])
+ }
}
}
+
- return dp[W]
+ return dp[W][V]
}

分割等和子集

01 背包变体,从若干物品中选择一部分,只能使用一次,能不能「恰好」填满 sum/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func canPartition(nums []int) bool {
sum := 0
for _, num := range nums {
sum += num
}

// 如果 sum 不是偶数肯定不可能对半分
if sum%2 != 0 {
return false
}
target := sum / 2

// 如果还是 -INF 则没法恰好装满
// 这里 nums 既是 重量 又是 价值
return knapsackExact(nums, nums, target, len(nums)) != math.MinInt
}

DAY 43(背包问题)

最后一块石头的重量 II

核心思想是将石头分为两堆,使得这两堆石头的总重量尽可能接近

可以转化为背包,选择一组物品,它们的总重量最大且不超过所有物品总重量的一半

这里石头重量也是既是重量又是价值

1
2
3
4
5
6
7
8
9
10
11
12
func lastStoneWeightII(stones []int) int {
sum := 0
for _, stone := range stones {
sum += stone
}
target := sum / 2

// 分成两堆,一堆是 dp[target],另一堆自然就是 sum - dp[target]
// 所以剩下的就是 (sum - dp[target]) - dp[target]
// 也就是 sum - 2 * dp[target]
return sum - 2*knapsack(stones, stones, target, len(stones))
}

目标和

我一开始只能写出一个递推的版本,而且写的有问题,喂给 GPT 他给我改好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findTargetSumWays(nums []int, target int) int {
// 使用 map 来存储每个和的可能方式数量
dp := make(map[int]int)
dp[0] = 1 // 初始化,和为0的方式有1种

for _, num := range nums {
// 创建一个新的 map 用于更新
next := make(map[int]int)
for sum, count := range dp {
// 对于每个可能的和,增加或减去当前数字
next[sum+num] += count
next[sum-num] += count
}
// 更新 dp 为 next,为下一轮迭代准备
dp = next
}

// 返回达到目标和的方式数量
return dp[target]
}

dp 思路有点巧妙,分成正号集合和负号集合,因为 正+负=sum 并且 正-负=target 所以解出

=(target+sum)/2正=(target+sum)/2

于是问题就转化成背包问题,选取一些元素正好凑成 (target+sum)/2 的个数

而如果不能整除,那就是无解

1
2
3
4
5
6
7
8
9
10
11
12
func findTargetSumWays(nums []int, target int) int {
sum := 0
for _, num := range nums {
sum += num
}

if (target+sum)%2 != 0 || target+sum < 0 {
return 0
}

return knapsackExactCount(nums, (target+sum)/2, len(nums))
}

一和零

可以转化为二维背包问题,两个维度的费用是 0 和 1 的个数,每个字符串的价值都是 1

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
func findMaxForm(strs []string, m int, n int) int {
zeros := make([]int, len(strs))
ones := make([]int, len(strs))
value := make([]int, len(strs))

// 计算每个字符串中 0 和 1 的数量
for i, s := range strs {
zeros[i], ones[i] = countZerosOnes(s) // 两个维度费用
value[i] = 1 // 所有字符串的价值都是 1
}

return knapsack2D(zeros, ones, value, m, n, len(strs))
}

func countZerosOnes(s string) (int, int) {
zeros, ones := 0, 0
for _, c := range s {
if c == '0' {
zeros++
} else {
ones++
}
}
return zeros, ones
}

DAY 44(背包问题)

完全背包

完全背包对比 01 背包的不同在于每种物品可以选择无限次,而不是只选择一次

完全背包的实现就是 01 背包的第二层遍历循序反一下

1
2
3
4
5
6
7
8
9
10
  func completeKnapsack(weight, value []int, W, N int) int {
dp := make([]int, W+1)
for i := 0; i < N; i++ { // 所有物品
- for j := W; j >= weight[i]; j-- { // 背包 W...weight[i]
+ for j := weight[i]; j <= W; j++ { // 背包 weight[i]...W
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}
return dp[W]
}

变体之「恰好装满」

「恰好装满」的改动与上面 01 的改动一样,只要求恰好装满都是这样改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   func completeKnapsackExact(weight, value []int, W, N int) int {
dp := make([]int, W+1)
+ for i := 1; i <= W; i++ { // 将 1...W 初始化为 -INF
+ dp[i] = math.MinInt
+ }
for i := 0; i < N; i++ { // 所有物品
for j := weight[i]; j <= W; j++ { // 背包 weight[i]...W
+ if dp[j-weight[i]] != math.MinInt { // 越界检查,仅处理正常值
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
+ }
}
}
return dp[W] // 如果还是 -INF 则没法恰好装满
}

变体之「恰好装满个数」

改动也是相同的,在完全背包的 commit 上(内层循序反转),再 commit 恰好装满个数

1
2
3
4
5
6
7
8
9
10
11
12
  func completeKnapsackExactCount(weight []int, W, N int) int {
dp := make([]int, W+1)
+ dp[0] = 1 // 无物品时,恰好装满重量为0的方式有一种

for i := 0; i < N; i++ { // 所有物品
for j := weight[i]; j <= W; j++ { // 背包 weight[i]...W
- dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
+ dp[j] += dp[j-weight[i]]
}
}
return dp[W] // 返回恰好装满背包的方案数
}

变体之「恰好装满排列个数」

之前都是求组合数(物品顺序不同算作同一方案),现在变成了求排列数

不同之处就是内外两层翻转一下,先遍历背包,再遍历物品

但是背包是 weight[i]...W ,而翻到外面了 i 还没有定义,所以需要里面再用 if 判断一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  func completeKnapsackExactCount2(weight []int, W, N int) int {
dp := make([]int, W+1)
dp[0] = 1 // 无物品时,恰好装满重量为0的方式有一种

- for i := 0; i < N; i++ { // 所有物品
- for j := weight[i]; j <= W; j++ { // 背包 weight[i]...W
+ for j := 0; j <= W; j++ { // 背包 weight[i]...W
+ for i := 0; i < N; i++ { // 所有物品
+ if j >= weight[i] {
dp[j] += dp[j-weight[i]]
+ }
}
}
return dp[W] // 返回恰好装满背包的方案数
}

零钱兑换 II

两个 buff 叠上去就行:完全背包 + 恰好装满求个数

1
2
3
func change(amount int, coins []int) int {
return completeKnapsackExactCount(coins,amount,len(coins))
}

组合总和 Ⅳ

叠三个 buff 🤣:完全背包 + 恰好装满求个数 + 排列计数

1
2
3
func combinationSum4(nums []int, target int) int {
return completeKnapsackExactCount2(nums,target,len(nums))
}

DAY 45(背包问题)

爬楼梯

用牛刀杀鸡,使用完全背包的思路做

  • 每次你可以爬 12 个台阶 -> 两个物品
  • 你有多少种不同的方法可以爬到楼顶 -> 完全背包,恰好装满,排列数
1
2
3
func climbStairs(n int) int {
return completeKnapsackExactCount2([]int{1,2},n,2)
}

零钱兑换

Buff 超多:完全背包(内层反向),恰好装满(初始化 -INF),而且不是物品最多,而是求最少

最多是 max,那最少就是 min,但是恰好装满已经是 -INF 了怎么办,那就初始化成 +INF 🤣

本题求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数

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 coinChange(coins []int, amount int) int {
value := make([]int, len(coins))
for i := range value {
value[i] = 1 // 每个硬币的价值是 1
}
ans := completeKnapsackExactMin(coins, value, amount, len(coins))
if ans == math.MaxInt { // 如果还是 +INF 则没法恰好装满
return -1
}
return ans
}

func completeKnapsackExactMin(weight, value []int, W, N int) int {
dp := make([]int, W+1)
for i := 1; i <= W; i++ { // 将 1...W 初始化为 +INF
dp[i] = math.MaxInt
}
for i := 0; i < N; i++ { // 所有物品
for j := weight[i]; j <= W; j++ { // 背包 weight[i]...W
if dp[j-weight[i]] != math.MaxInt { // 越界检查,仅处理正常值
dp[j] = min(dp[j], dp[j-weight[i]]+value[i])
}
}
}
return dp[W] // 如果还是 +INF 则没法恰好装满
}

完全平方数

使用纯背包的思路理解,物品就是一系列完全平方数 1,4,9,16...sqrt(n) ,背包大小是 n ,每个物品价值是 1

完全背包 + 恰好装满 + 物品最少,和上题的函数一样

1
2
3
4
5
6
7
8
9
10
func numSquares(n int) int {
m := int(math.Sqrt(float64(n)))
nums := make([]int, 0, m)
value := make([]int, 0, m)
for i := 1; i <= n; i++ {
nums = append(nums, i*i)
value = append(value, 1)
}
return completeKnapsackExactMin(nums, value, n, m)
}

融合思路可以就可以写成下面这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func numSquares(n int) int {
dp := make([]int, n+1)

for i := 1; i <= n; i++ {
dp[i] = math.MaxInt
}

for i := 1; i <= n; i++ {
num := i * i
for j := num; j <= n; j++ {
dp[j] = min(dp[j], dp[j-num]+1)
}
}

return dp[n]
}

DAY 46

单词拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func wordBreak(s string, wordDict []string) bool {
n := len(s)
dp := make([]bool, n+1)
exist := make(map[string]bool)
for i := 0; i < len(wordDict); i++ {
exist[wordDict[i]] = true
}
dp[0] = true

for i := 0; i <= n; i++ {
for j := 0; j < i; j++ {
if dp[j] && exist[s[j:i]] == true {
dp[i] = true
break
}
}
}

return dp[n]
}

DAY 47

休息

DAY 48(打家劫舍系列)

打家劫舍

经典 dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}

dp := make([]int, n)

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

for i := 2; i < n; i++ {
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
}

return dp[n-1]
}

打家劫舍 II

围成一圈的小技巧就是考虑掐头去尾两种情况

1
2
3
4
5
6
7
8
9
10
11
func rob(nums []int) int {

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

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

打家劫舍 III

变成了树形 dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func rob(root *TreeNode) int {
var dfs func(curr *TreeNode) []int
dfs = func(curr *TreeNode) []int {
if curr == nil {
return []int{0, 0}
}
l := dfs(curr.Left)
r := dfs(curr.Right)
robCurr := curr.Val + l[0] + r[0]
notRobCurr := max(l[0], l[1]) + max(r[0], r[1])
return []int{notRobCurr, robCurr}
}
ans := dfs(root)
return max(ans[0], ans[1])
}

DAY 49(股票系列)

买卖股票的最佳时机

不求复杂度最低,只求条理最清晰

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxProfit(prices []int) int {
/*
dp[i][0] 没买过
dp[i][1] 买了
dp[i][2] 卖了
*/

n := len(prices)
dp := make([][3]int, n)
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0

for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
}

return dp[n-1][2]
}

买卖股票的最佳时机 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxProfit(prices []int) int {
/*
dp[i][0] 不持有
dp[i][1] 持有
*/

n := len(prices)
dp := make([][2]int, n)
dp[0][0] = 0
dp[0][1] = -prices[0]

for i := 1; i < n; i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
}

return dp[n-1][0]
}

DAY 50(股票系列)

买卖股票的最佳时机 III

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 maxProfit(prices []int) int {
/*
dp[i][0] 没买过
dp[i][1] 第一次持有
dp[i][2] 第一次不持有
dp[i][3] 第二次持有
dp[i][4] 第二次不持有
*/

n := len(prices)
dp := make([][5]int, n)
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0
dp[0][3] = -prices[0]
dp[0][4] = 0

for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
}

return dp[n-1][4]
}

买卖股票的最佳时机 IV

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 maxProfit(k int, prices []int) int {
/*
dp[i][0] 没买过
dp[i][1] 第一次持有
dp[i][2] 第一次不持有
dp[i][3] 第二次持有
dp[i][4] 第二次不持有
dp[i][2*k-1] 第 k 次持有
dp[i][2*k] 第 k 次不持有
*/

n := len(prices)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, 2*k+1)
}
for i := 1; i < 2*k; i += 2 {
dp[0][i] = -prices[0]
}

for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0]
for j := 1; j <= 2*k; j++ {
if j%2 == 1 {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i])
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+prices[i])
}
}
}

return dp[n-1][2*k]
}

DAY 51(股票系列)

买卖股票的最佳时机含手续费

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxProfit(prices []int, fee int) int {
/*
dp[i][0] 不持有
dp[i][1] 持有
*/

n := len(prices)
dp := make([][2]int, n)
dp[0][0] = 0
dp[0][1] = -prices[0] - fee

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

return dp[n-1][0]
}

买卖股票的最佳时机含冷冻期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxProfit(prices []int) int {
/*
dp[i][0] 不持有
dp[i][1] 持有
dp[i][2] 在冷淡期
*/

n := len(prices)
dp := make([][3]int, n)
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0

for i := 1; i < n; i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][2])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
}

return max(dp[n-1][0], dp[n-1][2])
}

DAY 52

最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func lengthOfLIS(nums []int) int {
n := len(nums)
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}

for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j]+1)
}
}
}

ans := 0
for i := 0; i < n; i++ {
ans = max(ans, dp[i])
}
return ans
}

最长连续递增序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func findLengthOfLCIS(nums []int) int {
n := len(nums)
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}

for i := 1; i < n; i++ {
if nums[i-1] < nums[i] {
dp[i] = max(dp[i], dp[i-1]+1)
}
}

ans := 0
for i := 0; i < n; i++ {
ans = max(ans, dp[i])
}
return ans
}

最长重复子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findLength(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)

dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}

ans := 0
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
ans = max(ans, dp[i][j])
}
}
}

return ans
}

DAY 53

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)

dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}

for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}

return dp[m][n]
}

不相交的线

一开始想不出来,看了题解发现与上一题一模一样(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxUncrossedLines(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)

dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}

for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}

return dp[m][n]
}

最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxSubArray(nums []int) int {
n := len(nums)
dp := make([]int, n)

dp[0] = nums[0]
ans := nums[0]

for i := 1; i < n; i++ {
dp[i] = max(dp[i-1]+nums[i], nums[i])
ans = max(ans, dp[i])
}

return ans
}

DAY 54

休息

DAY 55(编辑距离系列)

判断子序列

编辑距离青春版,能于是能否从 t 删除部分字符得到 s

dp[i][j]s[:i]t[:j] 的最长公共子序列长度

1
2
3
4
当前字符相等:
dp[i-1][j-1] + 1
当前字符不相等:
放弃t[j](删除):dp[i][j-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isSubsequence(s string, t string) bool {
m, n := len(s), len(t)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}

for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s[i-1] == t[j-1] { // 因为s[:i]和t[:j]不包括s[i]和t[j],所以要-1
dp[i][j] = dp[i-1][j-1] + 1
} else { // 当前元素不同
dp[i][j] = dp[i][j-1] // 相当于删除 t[j]
}
}
}

return dp[m][n] == m
}

不同的子序列

dp[i][j]s[:i] 从出现 t[:j] 的个数

1
2
3
4
当前字符s[i-1]与t[j-1]相等:
使用s[i-1]+不使用s[i-1]:dp[i-1][j-1]+dp[i-1][j]
当前字符不相等:
不使用s[i-1]:dp[i-1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func numDistinct(s string, t string) int {
m, n := len(s), len(t)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}

for i := 0; i <= m; i++ {
dp[i][0] = 1
}

for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s[i-1] == t[j-1] {
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
} else {
dp[i][j] = dp[i-1][j]
}
}
}

return dp[m][n]
}

DAY 56

两个字符串的删除操作

与下一题相同,但是少了一个改的操作

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 minDistance(word1 string, word2 string) int {
n, m := len(word1), len(word2)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
}

for i := 0; i <= n; i++ {
dp[i][0] = i
}
for j := 0; j <= m; j++ {
dp[0][j] = j
}

for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
}
}
}

return dp[n][m]
}

编辑距离

1
2
3
4
5
6
7
8
当前字符word1[i-1]与word2[j-1]相等:
不操作:dp[i-1][j-1]
当前字符不相等:
min(
word1删除一个元素:dp[i-1][j]+1 (等同于word2增加一个元素)
word2删除一个元素:dp[i][j-1]+1 (等同于word1增加一个元素)
改:dp[i-1][j-1]+1
)
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 minDistance(word1 string, word2 string) int {
n, m := len(word1), len(word2)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
}

for i := 0; i <= n; i++ {
dp[i][0] = i
}
for j := 0; j <= m; j++ {
dp[0][j] = j
}

for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
}
}
}

return dp[n][m]
}

DAY 57

回文子串

dp[i][j]s[i:j] 是回文子串

1
2
3
4
5
s[i] != s[j]:
false
s[i] == s[j]:
abs(i-j)<=1: true
abs(i-j)>1: dp[i+1][j-1] // 因为i依赖后面,j依赖前面,所以i向前遍历,j向后遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func countSubstrings(s string) int {
n := len(s)
dp := make([][]bool, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
}

ans := 0
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] {
if j-i <= 1 || dp[i+1][j-1] {
ans++
dp[i][j] = true
}
}
}
}
return ans
}

最长回文子序列

dp[i][j]s[i:j] 的最长回文子序列

1
2
3
4
s[i]==s[j]:
dp[i+1][j-1]+2
s[i]!=s[j]:
max(dp[i+1][j],dp[i][j-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestPalindromeSubseq(s string) int {
n := len(s)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}

for i := 0; i < n; i++ {
dp[i][i] = 1
}

for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}

return dp[0][n-1]
}