menu

Leetcode Mr.How知其所以然之动态规划算法Leetcode归集主题模块

Leetcode Mr.How知其所以然之动态规划算法Leetcode归集主题模块

原创文章，版权所有，搬运文章，转发请注明polyaD，原文链接https://polyad.github.io/tags 如有任何问题或疑惑，请在后面留言或者发邮箱留言polyaluthor@gmail.com，加微信polyad或者qq数学算法开发10群 282642152进行探讨,请备注：Mr.How。
— 前言
  您好，欢迎来到我的引导学习记录博客，我是polayD, Mr.How先生。本系列依据《怎样解题》，George Polya的方法以及知其所以然模式启发，进行拓展而成。希望在这里，您能找到引导式学习的快乐，逐步建立与形成自己的知识同化模式，摆脱碎片化信息的烦扰，掌握快速学习与深度知识系统化的技能，期待与您共同进步。   信息碎片化的时代，大部分人只能随波逐流，特别是当没有形成系统化的知识模块，很多时候我们只能人云亦云，面对海量信息，无法判别重要性，相关性，有效性，普通的个人很难在信息洪流中找到自己的定位。深度式的知其所以然的引导式学习，可避开信息碎片化旋涡，同时突破信息茧房的束缚。下面波利亚将引领您，进入一个这个基础主题模块的海洋，带上自己的定位导航，抓紧好奇心的船舵，扬帆深入得在这片海洋里探索，前进，自我迭代进化。
**理念**
 首先，做什么事之前，先要设定一下我们的小目标， 我们的整体导航路径： 1.主题解析，先难后易，深入浅出，案例拆解，举一反三。
2.主要解决两个问题：如何思考这个问题？如何使用这个解决问题？
3.尽可能所有收集参考资料，用自己的语言进行复述回答。
4.计划将提供中英文版本。 5. 系列基础模块定位
  将如下基础主题模块化

**掌握的路径框架**

目录

动态规划算法经典问题归集
动态规划算法模板归集
动态规划算法工具归集
动态规划算法分类归集
    • Minimum (Maximum) Path to Reach a Target(到达目标的最值路径)
    • Distinct Ways(达到目标的不同方式总数)
    • Merging Intervals(区间合并)
    • DP on Strings(处理字符串的DP)
    • Decision Making(取舍决定)
全部215 DP problems 归集
    • 1.Linear DP
    • 2.Knapsack
    • 3.Multi Dimensions DP
    • 4.Interval DP
    • 5.bit DP
    • 6.Digit DP
    • 7.DP on Trees
    • 8.String DP
    • 9.Probability DP
    • 10.Classic DPs A.Cadane’s Algorithm
      B.LCS
      C.LIS
      D.2D Grid Traversal
      E.Cumulative Sum
      F.Hashmap (SubArray)
    • 11.DP + Alpha (Tricks/DS)
    • 12.Insertion DP
    • 13.Graph DP
    • 14.Memoization
    • 15.Binary Lifting
    • -16.Math
      复杂状态 DP problems 归集

      背包 DP
      区间 DP
      DAG 上的 DP
      树形 DP
      状压 DP
      数位 DP
      插头 DP
      计数 DP
      动态 DP
      概率 DP

动态规划算法经典问题归集
动态规划算法模板归集
动态规划算法工具归集

优化实现技术归集：

  • 尾递归优化

  • 二维数组优化

  • 二维转一维数组优化 DP 优化
    单调队列/单调栈优化
    斜率优化
    四边形不等式优化
    状态设计优化

动态规划算法分类归集

总结： 1.可选择，条件选择和最值选择。

  • 特征描述
    • Minimum (Maximum) Path to Reach a Target(到达目标的最值路径)
      给定一个目标，找出其最值路径，成本，总数等。
    • Distinct Ways(达到目标的不同方式总数)
      获取达到当前状态的所有方式总数
    • Merging Intervals(区间合并)
      从左边与右边的区间获取最优解
    • DP on Strings(处理字符串的DP)
      处理两个字符串的关系，根据条件选择结果。
    • Decision Making(取舍决定)
      给定一列数值，选择查找一个答案，选择或忽视当前值
  • 解题模板
    • Minimum (Maximum) Path to Reach a Target(到达目标的最值路径)
      最优子结构：调用最值函数，在多个结果中选择极值，max,min,sum 
      routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

      选择最优的值，返回 ```cpp for (int i = 1; i <= target; ++i) { for (int j = 0; j < ways.size(); ++j) { if (ways[j] <= i) { dp[i] = min(dp[i], dp[i - ways[j]]) + cost / path / sum; } } }

return dp[target]



- - Distinct Ways(达到目标的不同方式总数)

```cpp
routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] += dp[i - ways[j]];
       }
   }
}
 
return dp[target]
    • Merging Intervals(区间合并)
// from i to j
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]

for(int l = 1; l<n; l++) {
   for(int i = 0; i<n-l; i++) {
       int j = i+l;
       for(int k = i; k<j; k++) {
           dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]);
       }
   }
}
 
return dp[0][n-1]
    • DP on Strings(处理字符串的DP)
// i - indexing string s1
// j - indexing string s2
for (int i = 1; i <= n; ++i) {
   for (int j = 1; j <= m; ++j) {
       if (s1[i-1] == s2[j-1]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}
    • Decision Making(取舍决定)
// i - indexing a set of values
// j - options to ignore j values
for (int i = 1; i < n; ++i) {
   for (int j = 1; j <= k; ++j) {
       dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});
       dp[i][j-1] = max({dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i]});
   }
}

  • Leetcode问题列表

    • Minimum (Maximum) Path to Reach a Target(到达目标的最值路径)
      1. [64 Minimum Path Sum] (https://polyad.github.io/2021/08/07/Mr.How%E7%9F%A5%E5%85%B6%E6%89%80%E4%BB%A5%E7%84%B6Leetcode_64_Minimum_Path_Sum%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E5%92%8C%E9%97%AE%E9%A2%98%E6%A8%A1%E5%9D%97)
      2. 120 Triangle
      3. 174. Dungeon Game 4. Maximal Square
      5. Perfect Squares
      6. Coin Change
      7. Ones and Zeroes
      8. 2 Keys Keyboard
      9. Min Cost Climbing Stairs
      10. Minimum Number of Refueling Stops
      11. Minimum Falling Path Sum
      12. Minimum Cost For Tickets
      13. Last Stone Weight II
      14. Tiling a Rectangle with the Fewest Squares
      Similar Problems
      746. Min Cost Climbing Stairs Easy 931. Minimum Falling Path Sum Medium
      983. Minimum Cost For Tickets Medium
      650. 2 Keys Keyboard Medium
      279. Perfect Squares Medium
      1049. Last Stone Weight II Medium
      120. Triangle Medium
      474. Ones and Zeroes Medium
      221. Maximal Square Medium
      322. Coin Change Medium
      1240. Tiling a Rectangle with the Fewest Squares Hard
      174. Dungeon Game Hard
      871. Minimum Number of Refueling Stops Hard
    • Distinct Ways(达到目标的不同方式总数)
      1. Unique Paths
      2. Unique Paths II
      3. Climbing Stairs
      4. Combination Sum IV
      5. Partition Equal Subset Sum
      6. Target Sum
      7. Out of Boundary Paths
      8. Number of Longest Increasing Subsequence
      9. Knight Probability in Chessboard
      10. Domino and Tromino Tiling
      11. Minimum Swaps To Make Sequences Increasing
      12. Soup Servings
      13. Knight Dialer
      14. Number of Dice Rolls With Target Sum
      15. Count Vowels Permutation
      16. Dice Roll Simulation
      17. Number of Ways to Stay in the Same Place After Some Steps
      Similar Problems
      70. Climbing Stairs Easy
      1155. Number of Dice Rolls With Target Sum Medium
      62. Unique Paths Medium
      70. Climbing Stairs Easy
      1155. Number of Dice Rolls With Target Sum Medium
      688. Knight Probability in Chessboard Medium
      494. Target Sum Medium
      377. Combination Sum IV Medium
      935. Knight Dialer Medium
      1223. Dice Roll Simulation Medium
      416. Partition Equal Subset Sum Medium
      808. Soup Servings Medium
      790. Domino and Tromino Tiling Medium
      801. Minimum Swaps To Make Sequences Increasing
      673. Number of Longest Increasing Subsequence Medium
      63. Unique Paths II Medium
      576. Out of Boundary Paths Medium
      1269. Number of Ways to Stay in the Same Place After Some Steps Hard
      1220. Count Vowels Permutation Hard
    • Merging Intervals(区间合并)
      1. Unique Binary Search Trees
      2. Burst Balloons
      3. Guess Number Higher or Lower II
      4. Remove Boxes
      5. Minimum Cost to Merge Stones
      6. Minimum Score Triangulation of Polygon
      7. Minimum Cost Tree From Leaf Values
      Similar Problems
      1130. Minimum Cost Tree From Leaf Values Medium
      96. Unique Binary Search Trees Medium
      1039. Minimum Score Triangulation of Polygon Medium
      546. Remove Boxes Medium
      1000. Minimum Cost to Merge Stones Medium
      312. Burst Balloons Hard
      375. Guess Number Higher or Lower II Medium
    • DP on Strings(处理字符串的DP)
    • Decision Making(取舍决定)

#参考资料
—–
一级资料文献与书籍及重要作者
文献：
书籍：
博客：Dynamic Programming Patterns
Back Solved all dynamic programming (dp) problems in 7 months.
Algorithm Visualizer
动态规划到底有多难？
Huahua’s Tech Road
论坛：
视频：

二级资料：他人加工且有观点及大众资料
博客： 论坛：
视频：

返回顶部

评论：

技术文章推送

知其所以然主题模块分享

微信搜索公众号: How先生polyad
wechat 微信公众号：How先生polyad