動態規劃：

• 特點：核心是狀態轉移【由許多的重疊子問題組成】，

  • 當前狀態依賴于上一個狀態【遞推公式】，
  • 其次是初始化【對初始情況進行討論】
  • 遍歷順序：狀態的推到方向判斷【回文字串】

• 經典題型：

  • 基礎題型：

    • 斐波那契數：遞推公式的推導；
    • 爬樓的方法：多個狀態相互疊加得到下一個狀態；
    • 爬樓梯的消耗：多個狀態相互直接的min，得到下個狀態；
    • 不同路徑：推導公式在題目中，關鍵點在初始化；
    • 不同路徑II：有障礙，增加路徑判斷；
    • 整數拆分：貪心更簡單，動態規劃：拆分為【兩個數之和，至少三個數之和】取最大值；
    • 不同的二叉搜索樹：遞推公式的推導，左子樹，右子樹；

  • 背包問題：

    • 理論：

      • 背包容量：一定；
      • 物品
        • 體積：物品體積一定；
        • 價值：物品價值一定；
        • 數量：
          • 只有一個：01背包；
          • 無數個：完全背包；
          • 不同物品，數量不同：多重背包；
      • 整體上，分別是背包遍歷和物品遍歷，一個二維的動態規劃；
      • 遞推公式：
      • 初始化：是對物品dp[0][i]進行初始化；
      • 遍歷順序：先遍歷物品還是先遍歷背包都可，先遍歷物品更好理解；
      • 組合與排列取決于編列的順序：
        • 如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。【之前狀態是，左上角】
        • 如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。【還是有幾種方法】

    • 01背包：之前的狀態【使用的是左上角的值】

      • 分割子集，最后一塊石頭的重量：這兩題都是填充背包，遞推公式是求max最有價值的值；
      • 目標和：是一定能分割，求分割的方法有多少種，遞推公式是相加，還有初始化考察點，當物品體積為0的時；
      • 1和0：是一個三維的0-1背包問題；

    • 完全背包：之前狀態【以當前點為角的左上角【不包含當前點】】

    • 多重背包：

      • 相當于對物品在進行迭代一次【單次取一個，兩個，三個...】，轉化為01背包問題；

    • 總結：

      • 背包遞推公式：

        • 是否能裝滿，最多能裝多少，最大價值，最小個數：

          \[dp[j] = (min||max) (dp[j], dp[j - num[i]] + num[i]) \]

        • 問裝滿背包有多少種方法：

          \[dp[j] = dp[j] + dp[j - num[i]] \]

        • 遍歷順序：【物品 背包】

          • 01背包，完全背包：通常是先物品，在背包【組合】；
          • 完全背包：必須先背包，在物品【排列】；

        • 細節對于一維dp動態數組：

          • 01之前狀態：是由當前點的左上矩形狀態推導【不包含該點】；【對于物體，得從后向前遍歷】；
          • 完全背包：是由當前點的左上矩形狀態推導【包含該點】；【直接前向遍歷】

  • 打家劫舍：都是基于數組，循環鏈表，樹，等數據結構，遞推公式比較單一，考察在相關狀態數，其次在于初始化；

  • 股票問題：相當于一個狀態下多個節點的相互關系，交織出當前狀態，通常分為持節股票節點和不遲有節點【可以交易的最大筆數】，其次初始化和之前狀態數相關；

    • 從買賣一次到買賣多次【貪心，記錄已有的最小值，相互關系】；
    • 從最多買賣兩次到最多買賣k次【同一個狀態下的不同節點】，初始化；
    • 從冷凍期再到手續費【之前狀態的關系【遞推】】，初始化

  • 子序列問題：

    • 子序列【不連續】

      • 最長上升【下降】子序列：是對元素的刪除【雙層迭代，可以回溯，超時】，dp[i]以num[i]為結尾的子序列長度；‘

      • 最長公共子序列：

        if (nums[i] == num[j]) {
            dp[i][j] = dp[i - 1][j - 1]
        } else {
            //相對順序：正上和正左
        	dp[i][j] = max(dp[i - 1][j - 1],dp[i][j - 1])
        }
        

      • 不相交的線：同最長公共子序列【兩個數組的相對順序不變下的公共子序列】

    • 子序列【連續】

      • 最長連續上升【下降】序列：單層迭代【可以貪心】；

      • 最長公共子數組：【二維動態數組，dp】，以dp[i][j]的是num1[i]和num2[j]的最長子數組；

        if (nums[i] == num[j]) {
            dp[i][j] = dp[i - 1][j - 1]
        }
        //有序，是對角線有序，
        //相對順序：正上和正左
        dp[i][j] = max(dp[i - 1][j - 1],dp[i][j - 1])
        

      • 最大子數組和：可以貪心

    • 距離編輯

      • 判斷子序列：兩個子序列的并集【相對順序：正上和正左】；

        判斷字符串的的包含：KMP算法；

        動態規劃：擁有初始化，動態數組，并沒有雙指針性能好；

      • 子序列包含的個數：之前是判斷能不能，現在是有多少種方案；

      • 兩個字符串的刪除操作：之前是只允許刪除一個字符串；

      • 距離編輯：

        • 對一個字符串的刪除，插入，替換；
          • 刪除：dp[i][j - 1]；
          • 插入：相當于另一個字符串的刪除，dp[i - 1][j]；
          • 替換：相當于兩個字符串都刪除：dp[i - 1][j - 1]；

        關鍵在于dp的定義，用于簡化初始化，

        常見操作：刪除，插入，替換，

        類似于空間換效率，相比回溯方法，將所有可能計算出來，【當前狀態依賴于左上角的狀態】

    • 回文字串題型：

      • 回文子串的數量：考察遍歷順序
      • 最長回文子序列：在字串的基礎上，無需就是正上，正左取最大值；

      對于字符串的動態規劃：一般分為相不相等，兩種情況；

      五部曲：

      1. 確定動態數組dp的含義；
      2. 確定遞推公式【有時候，一個狀態下有多個節點，股票】
      3. dp的初始化【序列，dp的擴大定義，能更好的初始化】，
      4. 確定遍歷順序【背包問題，順序關系組合和排序，回文，順序關系遞推公式】
      5. 舉例：當前狀態和哪些之前狀態相關【正上，正左，斜對角，等等】；