Skip to content

Latest commit

 

History

History

09_dynamic_program

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
10. Regular Expression Matching.md
10. Regular Expression Matching.md
 
 
1043. Partition Array for Maximum Sum.md
1043. Partition Array for Maximum Sum.md
 
 
1048. Longest String Chain.md
1048. Longest String Chain.md
 
 
1062. Longest Repeating Substring.md
1062. Longest Repeating Substring.md
 
 
1140. Stone Game II.md
1140. Stone Game II.md
 
 
1143. Longest Common Subsequence.md
1143. Longest Common Subsequence.md
 
 
115. Distinct Subsequences.md
115. Distinct Subsequences.md
 
 
121. Best Time to Buy and Sell Stock.md
121. Best Time to Buy and Sell Stock.md
 
 
1216. Valid Palindrome III.md
1216. Valid Palindrome III.md
 
 
1235. Maximum Profit in Job Scheduling.md
1235. Maximum Profit in Job Scheduling.md
 
 
1277. Count Square Submatrices with All Ones.md
1277. Count Square Submatrices with All Ones.md
 
 
132. Palindrome Partitioning II.md
132. Palindrome Partitioning II.md
 
 
1335. Minimum Difficulty of a Job Schedule.md
1335. Minimum Difficulty of a Job Schedule.md
 
 
174. Dungeon Game.md
174. Dungeon Game.md
 
 
198. House Robber.md
198. House Robber.md
 
 
213. House Robber II.md
213. House Robber II.md
 
 
221. Maximal Square.md
221. Maximal Square.md
 
 
256. Paint House.md
256. Paint House.md
 
 
300. Longest Increasing Subsequence.md
300. Longest Increasing Subsequence.md
 
 
312. Burst Balloons.md
312. Burst Balloons.md
 
 
32. Longest Valid Parentheses.md
32. Longest Valid Parentheses.md
 
 
322. Coin Change.md
322. Coin Change.md
 
 
354. Russian Doll Envelopes.md
354. Russian Doll Envelopes.md
 
 
368. Largest Divisible Subset.md
368. Largest Divisible Subset.md
 
 
377. Combination Sum IV.md
377. Combination Sum IV.md
 
 
403. Frog Jump.md
403. Frog Jump.md
 
 
44. Wildcard Matching.md
44. Wildcard Matching.md
 
 
465. Optimal Account Balancing.md
465. Optimal Account Balancing.md
 
 
472. Concatenated Words.md
472. Concatenated Words.md
 
 
518. Coin Change II.md
518. Coin Change II.md
 
 
62. Unique Paths.md
62. Unique Paths.md
 
 
639. Decode Ways II.md
639. Decode Ways II.md
 
 
64. Minimum Path Sum.md
64. Minimum Path Sum.md
 
 
674. Longest Continuous Increasing Subsequence.md
674. Longest Continuous Increasing Subsequence.md
 
 
70. Climbing Stairs.md
70. Climbing Stairs.md
 
 
712. Minimum ASCII Delete Sum for Two Strings.md
712. Minimum ASCII Delete Sum for Two Strings.md
 
 
718. Maximum Length of Repeated Subarray.md
718. Maximum Length of Repeated Subarray.md
 
 
72. Edit Distance.md
72. Edit Distance.md
 
 
740. Delete and Earn.md
740. Delete and Earn.md
 
 
87. Scramble String.md
87. Scramble String.md
 
 
91. Decode Ways.md
91. Decode Ways.md
 
 
926. Flip String to Monotone Increasing.md
926. Flip String to Monotone Increasing.md
 
 
97. Interleaving String.md
97. Interleaving String.md
 
 
README.md
README.md
 
 

README.md

动态规划

  • 问题

    • 解决有重复子问题的最优化问题，注意理解树、递归、dfs、回溯到动态规划的这样一条线
    • 通过保存子问题的解，避免重复计算
    • 思路：数学归纳法(Mathematical Induction)，base case
      • 确定dp状态的含义
      • 递推方程与初始化。通过状态枚举帮助完成递推方程
      • 循环方式

  • 类型

    • top-down (记忆化dfs)
    • bottom-up (循环)

  • 类型

    • 记忆化搜索（DFS + Memoization Search）
    • for循环方式的动态规划，非Memoization Search方式。DP可以在多项式时间复杂度内解决DFS需要指数级别的问题。常见的题目包括找最大最小，找可行性，找总方案数等，一般结果是一个Integer或者Boolean
    • 结合了BFS和动态规划，或者DFS和动态规划
    • 结果: 有时候DP不是最后的结果，还需要用min/max/sum(dp)

  • 常见

    • 背包问题(Knapsack problem)
      • 递推公式中根据本次加入的数据(重量)决定了向上查找的状态
      • 01背包
      • 完全背包 Unbounded Knapsack
    • 打劫问题
    • 字符串子序列
      • 编辑距离
      • 最长公共字串
      • 回文串
    • 股票问题

背包

01背包二维

# dp[i][j]：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
# dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]

01背包一维

# dp[0,...,W] = 0
# for i = 1,...,N
#     for j = W,...,w[i] // 必须逆向枚举!!!
#         dp[j] = max(dp[j], dp[j−w[i]]+v[i])

恰好装满

  • 没有恰好装满背包的限制，将dp全部初始化成0就可以
  • 如果有恰好装满的限制，那只应该将dp[0,...,N][0]初始为0，其它dp值均初始化为-inf

求方案总数

  • dp[i][j] = sum(dp[i−1][j], dp[i]j−w[i]]) // j >= w[i]

求最优方案

  • 一般动态规划问题输出方案的方法：记录下每个状态的最优值是由哪一个策略推出来的，这样便可根据这条策略找到上一个状态，从上一个状态接着向前推即可

参考