IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
    • 登录 注册

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

    NX の 博客发表于 2023-12-01 11:12:28
    love 0

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

    变体之「多维背包」

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

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

    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

    于是问题就转化成背包问题，选取一些元素正好凑成 (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

    爬楼梯

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

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


沪ICP备19023445号-2号
友情链接