动态规划

动态规划 Dynamic Programming

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

入门

完整掌握一道动态规划题目，需要在做题前|做题中|AC后思考以下问题：

• DP数组及下标的实际含义，得考虑清楚
• 递推公式
• DP数组如何初始化
• 遍历顺序
• 打印DP数组

基础问题

• 斐波那契数列
  • dp[i] 即为 fib(i)
  • dp[i] = dp[i-1] + dp[i-2]
• 爬楼梯
  • dp[i] 为到第 i 层有几种方法
  • 条件：每一次可以爬两层或爬一层
  • dp[i] = dp[i - 1] * 1 + dp[i - 2] * 1
• 最小花费爬楼梯
  • dp[i] 为到第 i 层的最小花费
  • 条件：每一次可以爬一层或两层
  • dp[i] = Math.min(dp[i-2] + cost[i-2], dp[i-1] + cost[i- 1])
• 不同路径(从[0,0]到[m,n]的路径数)
  • dp[i][j] 为到[i,j]的路径数
  • 条件：每一步只能向右走或向下走
  • if(i>0) dp[i][j] += dp[i-1][j]
  • if(j>0) dp[i][j] += dp[i][j-1]

• 不同路径II(在上题基础上新加了障碍物，障碍物dp[i][j]为0即可解决)

• 整数拆分
  • 描述：把一个整数拆分为几个数，使拆分乘积最大化，求最大乘积
  • 核心推导：数字n拆分后最大乘积可能的来源? 拆2个？3个？最少拆两个吧
    • 第一种可能：i * (n-i)
    • 第二种可能：i * dp[n-i]
    • 所以要遍历拆分，取最大

    •  dp[2] = 1
       for (let i = 3; i < n + 1; i++) {
            for (let j = 0; j < i; j++) {
                dp[i] = Math.max(
                    j * (i - j),
                    j * dp[i - j],
                    dp[i]
                )
            }
        }
      

• 不同的二叉搜索树
  • 给n个节点，求能组成多少种二叉搜索树
  • 初始化：dp[0] = 0; dp[1] = 1
  • 核心推导：n个节点组成二叉搜索树和之前的dp[n-1],dp[n-2]..有关系没？
    • 有的，遍历n个节点，依次作为根节点
    • 那么左子树的种类就是dp[leftNodeNum], 右子树同理

    •   for (let i = 2; i < n + 1; i++) {
          // 对于i个元素
          for (let j = 0; j < i; j++) {
      
              // 把第j个元素作为根
              const leftNodeNum = j
              const rightNodeNum = i - j - 1
      
              if (leftNodeNum == 0 || rightNodeNum == 0) {
                  dp[i] += dp[leftNodeNum]
                  dp[i] += dp[rightNodeNum]
              } else {
                  dp[i] += dp[leftNodeNum] * dp[rightNodeNum]
              }
          }
      }
      

背包问题

wc上强度了

• 分割等和子集
  • 题目理解
    • 描述：给一个nums数组，判定该数组是否可以分为两个和相等的子集
    • 题意剖析：需要恰好分为两个子集，且和相等，那这个和必然是整个数组之和的一半，那就变成了求子集里，和为sum/2的子集；也就变成了给你一堆物品和一个目标，判断能不能选出若干个物品（每个数只能用一次），使得满足目标，这就变成了01背包问题。至于另一半嘛，如果我能找出一个子集和为总和的一半，那么另一半自动就满足了。
    • 最终题目：你有n个物品，这物品i的重量为nums[i],价值为nums[j]，你需要判断一个容量为sum/2的背包能装的最大价值是否是sum/2
  • DP实现
    • dp[i][j]:针对0-i个物品，容量为j的背包能装的最大价值
    • 初始化dp[i][0]为0，dp[0][j]遍历判断能不能装第一个物品
    • 典型的01背包

        for (let i = 1; i < nums.length; i++) { // 遍历物品
                  
            let thingValue = nums[i]
            let thingWeight = nums[i]
      
            for (let j = 1; j < partSum + 1; j++) { // 遍历背包容量
      
                if (j < thingWeight) { // 背包容量比物品容量还小，别考虑这个物品了
                    dp[i][j] = dp[i - 1][j]
                    continue
                }
                      
                // 有可能塞进来
                const v1 = dp[i - 1][j] // 不塞
                const v2 = dp[i - 1][j - thingWeight] + thingValue // 塞
                dp[i][j] = Math.max(v1, v2)
      
            }
      
        }
      
      

• 最后一块石头的重量
  • 题目理解
    • 描述：给Stones，其中石头两两可以攻击破坏，求最终剩余的石头最小重量
    • 题意剖析：两两可破坏，求最终剩最小，那就变成了尽可能分为两组大小相等的石头，这就变成了上一题-求和相等的子集，变成了找重量为sum/2的包的价值
    • 最终题目：你有n个物品，每个物品价值为stones[i],重量为stones[i]，求重量为sum/2的包的价值和sum/2之间的diff

打家劫舍

股票问题

子序列问题