『代码随想录』动态规划（Dynamic Programming）

DAY 38

斐波那契数

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]
}

爬楼梯

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]
}

使用最小花费爬楼梯

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

不同路径

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

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])

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])

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 的背包可以获得的最大价值

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 背包

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

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

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]
}

变体之「恰好装满」

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

   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] 的含义就变成方案个数了，并且转移方程也变了，但是要牢记不变的遍历顺序

  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] // 返回恰好装满背包的方案数
  }

变体之「多维背包」

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

每多一个维度就加一维 dp 和 for 就行，下面以二维举例

  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

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

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

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

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

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 他给我改好了

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 的个数

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

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

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 背包的第二层遍历循序反一下

  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 的改动一样，只要求恰好装满都是这样改

   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 恰好装满个数

  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 判断一下

  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 叠上去就行：完全背包 + 恰好装满求个数

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

组合总和 Ⅳ

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

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

DAY 45（背包问题）

爬楼梯

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

• 每次你可以爬 1 或 2 个台阶 -> 两个物品
• 你有多少种不同的方法可以爬到楼顶 -> 完全背包，恰好装满，排列数

func climbStairs(n int) int {
    return completeKnapsackExactCount2([]int{1,2},n,2)
}

零钱兑换

Buff 超多：完全背包（内层反向），恰好装满（初始化 -INF），而且不是物品最多，而是求最少

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

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

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

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

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)
}

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

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

单词拆分

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

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

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

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

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（股票系列）

买卖股票的最佳时机

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

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

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

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

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（股票系列）

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

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]
}

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

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

最长递增子序列

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
}

最长连续递增序列

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
}

最长重复子数组

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

最长公共子序列

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]
}

不相交的线

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

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]
}

最大子数组和

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] 的最长公共子序列长度

当前字符相等：
	dp[i-1][j-1] + 1 
当前字符不相等：
	放弃t[j]（删除）：dp[i][j-1]

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] 的个数

当前字符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]

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

两个字符串的删除操作

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

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]
}

编辑距离

当前字符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
    )

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] 是回文子串

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向后遍历

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] 的最长回文子序列

s[i]==s[j]:
	dp[i+1][j-1]+2
s[i]!=s[j]:
	max(dp[i+1][j],dp[i][j-1])

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]
}