動態規劃

發表於 | 分類於 ，

一般形式就是求極值，核心思想是窮舉 + 重疊子問題。狀態、選擇、base case

動態規劃框架

1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

壓縮動態規劃

注意到dp[i][j] 都是由 dp[i-1][..] 轉移過來的，之前的數據都不需要了，所以可以將二維壓縮成一維，節省空間複雜度。

題目

動態規劃一般形式，求極值

動態規劃基本問題 [8]

  • 509 Fibonacci Number (Easy)

  • 322 Coin Change (Medium)

  • *983 Minimum Cost For Tickets (Medium)

  • 931 Minimum Falling Path Sum (Medium)

  • 64 Minimum Path Sum (Medium)

  • 70 Climbing Stairs (Easy)

  • 62 Unique Paths (Easy)

    *63 Unique Paths II (Medium)

子序列問題 [14]

  • 53 Maximum Subarray (Easy)

    *918 Maximum Sum Circular Subarray (Medium)
    1567 Maximum Length of Subarray With Positive Product (Medium)

  • 300 Longest Increasing Subsequence (Medium)

  • 354 Russian Doll Envelopes

  • 1143 Longest Common Subsequence (Medium)

  • 583 Delete Operation for Two Strings (Medium)

  • 712 Minimum ASCII Delete Sum for Two Strings (Medium)

  • 72 Edit Distance (Hard)

  • 1312 Minimum Insertion Steps to Make a String Palindrome

  • 516 Longest Palindromic Subsequence (Medium)

  • *5 Longest Palindromic Substring (Medium)

  • 647 Palindromic Substrings

  • 10 Regular Expression Matching (Hard)

背包問題 [3]

  • 518 Coin Change 2 (Medium)

  • 416 Partition Equal Subset Sum (Medium)

  • 494 Target Sum (Medium)

  • 2466 Count Ways To Build Good Strings

股票問題 [6]

  • 121 Best Time to Buy and Sell Stock (Easy)
  • 188 Best Time to Buy and Sell Stock IV (Hard)
  • 122 Best Time to Buy and Sell Stock II (Easy)
  • 123 Best Time to Buy and Sell Stock III (Hard)
  • 309 Best Time to Buy and Sell Stock with Cooldown (Medium)
  • 714 Best Time to Buy and Sell Stock with Cooldown (Medium)

搶劫問題 [3]

  • 198 House Robber (Medium)
  • 213 House Robber II (Medium)
  • 337 House Robber III (Medium)

貪心問題 [8]

  • 134 Gas Station (Medium)

  • 1024 Video Stitching (Medium)

  • 453 Minimum Moves to Equal Array Elements (Easy)

  • 435 Non-overlapping Intervals (Medium)

  • 452 Minimum Number of Arrows to Burst Balloons (Medium)

  • 55 Jump Game (Medium)

  • 45 Jump Game II (Medium)

  • 870 Advantage Shuffle (Medium)

遊戲問題 [10]

  • 174 Dungeon Game (Hard)

  • 514 Freedom Trail (Hard)

  • 787 Cheapest Flights Within K Stops (Medium)

  • 887 Super Egg Drop (Hard)

  • 312 Burst Balloons (Hard)

  • 877 Stone Game (Medium)

  • 651 4 Keys Keyboard (Medium)

  • 292 Nim Game (Easy)

  • 877 Stone Game (Medium)

  • 319 Bulb Switcher (Medium)

補充 [19]

  • 1137 N-th Tribonacci Number

  • 746 Min Cost Climbing Stairs

  • 204 Count Primes

  • 740 Delete and Earn

  • 120 Triangle

  • 1014 Best Sightseeing Pair

  • 397 Integer Replacement

  • 1567 Maximum Length of Subarray With Positive Product (Medium)

  • 377 Combination Sum IV

  • 139 Word Break (Medium)

  • 140 Word Break II (Hard)

  • *413 Arithmetic Slices

  • 91 Decode Ways

  • 279 Perfect Squares

  • 799 Champagne Tower

two dp

  • 918 Maximum Sum Circular Subarray
  • 152 Maximum Product Subarray (Medium)
  • 42 Trapping Rain Water
  • 334 Increasing Triplet Subsequence