Skip to content

Latest commit

 

History

History
645 lines (622 loc) · 54.5 KB

0000-26-dynamic-programming.adoc

File metadata and controls

645 lines (622 loc) · 54.5 KB

Dynamic Programming 动态规划

动态规划的设计思想：「不是直接面对问题求解，而是从一个最小规模的问题开始，新问的最优解均是由比它规模还小的子问题的最优解转换得到，在求解的过程中记录每一步的结果，直至所要求的问题得到解」。

{image_attr}

动态规划的五部曲：

  1. 确定 dp 数组（dp table）以及下标的含义

  2. 确定递推公式

  3. dp 数组如何初始化

  4. 确定遍历顺序

  5. 举例推导 dp 数组

1. 经典题目

  1. 5. Longest Palindromic Substring

  2. 10. Regular Expression Matching

  3. 22. Generate Parentheses

  4. 32. Longest Valid Parentheses

  5. 42. Trapping Rain Water

  6. 44. Wildcard Matching

  7. 45. Jump Game II

  8. 53. Maximum Subarray

  9. 55. Jump Game

  10. 62. Unique Paths

  11. 63. Unique Paths II

  12. 64. Minimum Path Sum

  13. 70. Climbing Stairs

  14. 72. Edit Distance

  15. 85. Maximal Rectangle

  16. 87. Scramble String

  17. 91. Decode Ways

  18. 95. Unique Binary Search Trees II

  19. 96. Unique Binary Search Trees

  20. 97. Interleaving String

  21. 115. Distinct Subsequences

  22. 118. Pascal’s Triangle

  23. 119. Pascal’s Triangle II

  24. 120. Triangle

  25. 121. Best Time to Buy and Sell Stock

  26. 122. Best Time to Buy and Sell Stock II

  27. 123. Best Time to Buy and Sell Stock III

  28. 124. Binary Tree Maximum Path Sum

  29. 131. Palindrome Partitioning

  30. 132. Palindrome Partitioning II

  31. 139. Word Break

  32. 140. Word Break II

  33. 152. Maximum Product Subarray

  34. 174. Dungeon Game

  35. 188. Best Time to Buy and Sell Stock IV

  36. 198. House Robber

  37. 213. House Robber II

  38. 221. Maximal Square

  39. 233. Number of Digit One

  40. 241. Different Ways to Add Parentheses

  41. 256. Paint House

  42. 264. Ugly Number II

  43. 265. Paint House II

  44. 276. Paint Fence

  45. 279. Perfect Squares

  46. 294. Flip Game II

  47. 300. Longest Increasing Subsequence

  48. 309. Best Time to Buy and Sell Stock with Cooldown

  49. 312. Burst Balloons

  50. 313. Super Ugly Number

  51. 322. Coin Change

  52. 329. Longest Increasing Path in a Matrix

  53. 333. Largest BST Subtree

  54. 337. House Robber III

  55. 338. Counting Bits

  56. 343. Integer Break

  57. 351. Android Unlock Patterns

  58. 354. Russian Doll Envelopes

  59. 357. Count Numbers with Unique Digits

  60. 361. Bomb Enemy

  61. 368. Largest Divisible Subset

  62. 375. Guess Number Higher or Lower II

  63. 376. Wiggle Subsequence

  64. 377. Combination Sum IV

  65. 392. Is Subsequence

  66. 396. Rotate Function

  67. 397. Integer Replacement

  68. 403. Frog Jump

  69. 410. Split Array Largest Sum

  70. 413. Arithmetic Slices

  71. 416. Partition Equal Subset Sum

  72. 418. Sentence Screen Fitting

  73. 435. Non-overlapping Intervals

  74. 446. Arithmetic Slices II - Subsequence

  75. 458. Poor Pigs

  76. 464. Can I Win

  77. 465. Optimal Account Balancing

  78. 466. Count The Repetitions

  79. 467. Unique Substrings in Wraparound String

  80. 471. Encode String with Shortest Length

  81. 472. Concatenated Words

  82. 473. Matchsticks to Square

  83. 474. Ones and Zeroes

  84. 486. Predict the Winner

  85. 487. Max Consecutive Ones II

  86. 488. Zuma Game

  87. 494. Target Sum

  88. 509. Fibonacci Number

  89. 514. Freedom Trail

  90. 516. Longest Palindromic Subsequence

  91. 518. Coin Change II

  92. 526. Beautiful Arrangement

  93. 542. 01 Matrix

  94. 546. Remove Boxes

  95. 552. Student Attendance Record II

  96. 553. Optimal Division

  97. 562. Longest Line of Consecutive One in Matrix

  98. 568. Maximum Vacation Days

  99. 576. Out of Boundary Paths

  100. 583. Delete Operation for Two Strings

  101. 600. Non-negative Integers without Consecutive Ones

  102. 629. K Inverse Pairs Array

  103. 634. Find the Derangement of An Array

  104. 638. Shopping Offers

  105. 639. Decode Ways II

  106. 646. Maximum Length of Pair Chain

  107. 647. Palindromic Substrings

  108. 650. 2 Keys Keyboard

  109. 651. 4 Keys Keyboard

  110. 656. Coin Path

  111. 664. Strange Printer

  112. 673. Number of Longest Increasing Subsequence

  113. 678. Valid Parenthesis String

  114. 688. Knight Probability in Chessboard

  115. 689. Maximum Sum of 3 Non-Overlapping Subarrays

  116. 691. Stickers to Spell Word

  117. 698. Partition to K Equal Sum Subsets

  118. 712. Minimum ASCII Delete Sum for Two Strings

  119. 714. Best Time to Buy and Sell Stock with Transaction Fee

  120. 718. Maximum Length of Repeated Subarray

  121. 727. Minimum Window Subsequence

  122. 730. Count Different Palindromic Subsequences

  123. 740. Delete and Earn

  124. 741. Cherry Pickup

  125. 746. Min Cost Climbing Stairs

  126. 750. Number Of Corner Rectangles

  127. 764. Largest Plus Sign

  128. 773. Sliding Puzzle

  129. 787. Cheapest Flights Within K Stops

  130. 788. Rotated Digits

  131. 790. Domino and Tromino Tiling

  132. 792. Number of Matching Subsequences

  133. 799. Champagne Tower

  134. 801. Minimum Swaps To Make Sequences Increasing

  135. 805. Split Array With Same Average

  136. 808. Soup Servings

  137. 813. Largest Sum of Averages

  138. 818. Race Car

  139. 823. Binary Trees With Factors

  140. 828. Count Unique Characters of All Substrings of a Given String

  141. 834. Sum of Distances in Tree

  142. 837. New 21 Game

  143. 838. Push Dominoes

  144. 845. Longest Mountain in Array

  145. 847. Shortest Path Visiting All Nodes

  146. 871. Minimum Number of Refueling Stops

  147. 873. Length of Longest Fibonacci Subsequence

  148. 877. Stone Game

  149. 879. Profitable Schemes

  150. 887. Super Egg Drop

  151. 894. All Possible Full Binary Trees

  152. 898. Bitwise ORs of Subarrays

  153. 902. Numbers At Most N Given Digit Set

  154. 903. Valid Permutations for DI Sequence

  155. 907. Sum of Subarray Minimums

  156. 913. Cat and Mouse

  157. 918. Maximum Sum Circular Subarray

  158. 920. Number of Music Playlists

  159. 926. Flip String to Monotone Increasing

  160. 931. Minimum Falling Path Sum

  161. 935. Knight Dialer

  162. 940. Distinct Subsequences II

  163. 943. Find the Shortest Superstring

  164. 956. Tallest Billboard

  165. 960. Delete Columns to Make Sorted III

  166. 964. Least Operators to Express Number

  167. 968. Binary Tree Cameras

  168. 975. Odd Even Jump

  169. 978. Longest Turbulent Subarray

  170. 983. Minimum Cost For Tickets

  171. 996. Number of Squareful Arrays

  172. 1000. Minimum Cost to Merge Stones

  173. 1012. Numbers With Repeated Digits

  174. 1014. Best Sightseeing Pair

  175. 1024. Video Stitching

  176. 1025. Divisor Game

  177. 1027. Longest Arithmetic Subsequence

  178. 1031. Maximum Sum of Two Non-Overlapping Subarrays

  179. 1035. Uncrossed Lines

  180. 1039. Minimum Score Triangulation of Polygon

  181. 1043. Partition Array for Maximum Sum

  182. 1048. Longest String Chain

  183. 1049. Last Stone Weight II

  184. 1062. Longest Repeating Substring

  185. 1066. Campus Bikes II

  186. 1067. Digit Count in Range

  187. 1092. Shortest Common Supersequence

  188. 1105. Filling Bookcase Shelves

  189. 1125. Smallest Sufficient Team

  190. 1130. Minimum Cost Tree From Leaf Values

  191. 1137. N-th Tribonacci Number

  192. 1139. Largest 1-Bordered Square

  193. 1140. Stone Game II

  194. 1143. Longest Common Subsequence

  195. 1147. Longest Chunked Palindrome Decomposition

  196. 1155. Number of Dice Rolls With Target Sum

  197. 1162. As Far from Land as Possible

  198. 1182. Shortest Distance to Target Color

  199. 1186. Maximum Subarray Sum with One Deletion

  200. 1187. Make Array Strictly Increasing

  201. 1191. K-Concatenation Maximum Sum

  202. 1216. Valid Palindrome III

  203. 1218. Longest Arithmetic Subsequence of Given Difference

  204. 1220. Count Vowels Permutation

  205. 1223. Dice Roll Simulation

  206. 1227. Airplane Seat Assignment Probability

  207. 1230. Toss Strange Coins

  208. 1235. Maximum Profit in Job Scheduling

  209. 1246. Palindrome Removal

  210. 1255. Maximum Score Words Formed by Letters

  211. 1259. Handshakes That Don’t Cross

  212. 1262. Greatest Sum Divisible by Three

  213. 1269. Number of Ways to Stay in the Same Place After Some Steps

  214. 1277. Count Square Submatrices with All Ones

  215. 1278. Palindrome Partitioning III

  216. 1289. Minimum Falling Path Sum II

  217. 1301. Number of Paths with Max Score

  218. 1312. Minimum Insertion Steps to Make a String Palindrome

  219. 1320. Minimum Distance to Type a Word Using Two Fingers

  220. 1326. Minimum Number of Taps to Open to Water a Garden

  221. 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

  222. 1335. Minimum Difficulty of a Job Schedule

  223. 1340. Jump Game V

  224. 1349. Maximum Students Taking Exam

  225. 1359. Count All Valid Pickup and Delivery Options

  226. 1363. Largest Multiple of Three

  227. 1372. Longest ZigZag Path in a Binary Tree

  228. 1373. Maximum Sum BST in Binary Tree

  229. 1387. Sort Integers by The Power Value

  230. 1388. Pizza With 3n Slices

  231. 1395. Count Number of Teams

  232. 1397. Find All Good Strings

  233. 1402. Reducing Dishes

  234. 1406. Stone Game III

  235. 1411. Number of Ways to Paint N × 3 Grid

  236. 1416. Restore The Array

  237. 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

  238. 1425. Constrained Subsequence Sum

  239. 1434. Number of Ways to Wear Different Hats to Each Other

  240. 1444. Number of Ways of Cutting a Pizza

  241. 1449. Form Largest Integer With Digits That Add up to Target

  242. 1458. Max Dot Product of Two Subsequences

  243. 1463. Cherry Pickup II

  244. 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls

  245. 1473. Paint House III

  246. 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

  247. 1478. Allocate Mailboxes

  248. 1483. Kth Ancestor of a Tree Node

  249. 1493. Longest Subarray of 1’s After Deleting One Element

  250. 1494. Parallel Courses II

  251. 1504. Count Submatrices With All Ones

  252. 1510. Stone Game IV

  253. 1524. Number of Sub-arrays With Odd Sum

  254. 1525. Number of Good Ways to Split a String

  255. 1526. Minimum Number of Increments on Subarrays to Form a Target Array

  256. 1531. String Compression II

  257. 1537. Get the Maximum Score

  258. 1547. Minimum Cost to Cut a Stick

  259. 1548. The Most Similar Path in a Graph

  260. 1553. Minimum Number of Days to Eat N Oranges

  261. 1563. Stone Game V

  262. 1567. Maximum Length of Subarray With Positive Product

  263. 1569. Number of Ways to Reorder Array to Get Same BST

  264. 1575. Count All Possible Routes

  265. 1578. Minimum Time to Make Rope Colorful

  266. 1594. Maximum Non Negative Product in a Matrix

  267. 1595. Minimum Cost to Connect Two Groups of Points

  268. 1611. Minimum One Bit Operations to Make Integers Zero

  269. 1617. Count Subtrees With Max Distance Between Cities

  270. 1621. Number of Sets of K Non-Overlapping Line Segments

  271. 1626. Best Team With No Conflicts

  272. 1638. Count Substrings That Differ by One Character

  273. 1639. Number of Ways to Form a Target String Given a Dictionary

  274. 1641. Count Sorted Vowel Strings

  275. 1643. Kth Smallest Instructions

  276. 1653. Minimum Deletions to Make String Balanced

  277. 1654. Minimum Jumps to Reach Home

  278. 1655. Distribute Repeating Integers

  279. 1659. Maximize Grid Happiness

  280. 1668. Maximum Repeating Substring

  281. 1671. Minimum Number of Removals to Make Mountain Array

  282. 1681. Minimum Incompatibility

  283. 1682. Longest Palindromic Subsequence II

  284. 1687. Delivering Boxes from Storage to Ports

  285. 1690. Stone Game VII

  286. 1691. Maximum Height by Stacking Cuboids

  287. 1692. Count Ways to Distribute Candies

  288. 1696. Jump Game VI

  289. 1714. Sum Of Special Evenly-Spaced Elements In Array

  290. 1723. Find Minimum Time to Finish All Jobs

  291. 1728. Cat and Mouse II

  292. 1735. Count Ways to Make Array With Product

  293. 1745. Palindrome Partitioning IV

  294. 1746. Maximum Subarray Sum After One Operation

  295. 1749. Maximum Absolute Sum of Any Subarray

  296. 1751. Maximum Number of Events That Can Be Attended II

  297. 1755. Closest Subsequence Sum

  298. 1770. Maximum Score from Performing Multiplication Operations

  299. 1771. Maximize Palindrome Length From Subsequences

  300. 1774. Closest Dessert Cost

  301. 1786. Number of Restricted Paths From First to Last Node

  302. 1787. Make the XOR of All Segments Equal to Zero

  303. 1799. Maximize Score After N Operations

  304. 1815. Maximum Number of Groups Getting Fresh Donuts

  305. 1824. Minimum Sideway Jumps

  306. 1857. Largest Color Value in a Directed Graph

  307. 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

  308. 1871. Jump Game VII

  309. 1872. Stone Game VIII

  310. 1879. Minimum XOR Sum of Two Arrays

  311. 1883. Minimum Skips to Arrive at Meeting On Time

  312. 1884. Egg Drop With 2 Eggs and N Floors

  313. 1888. Minimum Number of Flips to Make the Binary String Alternating

  314. 1896. Minimum Cost to Change the Final Value of Expression

  315. 1900. The Earliest and Latest Rounds Where Players Compete

  316. 1908. Game of Nim

  317. 1911. Maximum Alternating Subsequence Sum

  318. 1916. Count Ways to Build Rooms in an Ant Colony

  319. 1928. Minimum Cost to Reach Destination in Time

  320. 1931. Painting a Grid With Three Different Colors

  321. 1937. Maximum Number of Points with Cost

  322. 1947. Maximum Compatibility Score Sum

  323. 1955. Count Number of Special Subsequences

  324. 1959. Minimum Total Space Wasted With K Resizing Operations

  325. 1976. Number of Ways to Arrive at Destination

  326. 1977. Number of Ways to Separate Numbers

  327. 1981. Minimize the Difference Between Target and Chosen Elements

  328. 1986. Minimum Number of Work Sessions to Finish the Tasks

  329. 1987. Number of Unique Good Subsequences

  330. 1994. The Number of Good Subsets

  331. 1997. First Day Where You Have Been in All the Rooms

  332. 2002. Maximum Product of the Length of Two Palindromic Subsequences

  333. 2003. Smallest Missing Genetic Value in Each Subtree

  334. 2005. Subtree Removal Game with Fibonacci Tree

  335. 2008. Maximum Earnings From Taxi

  336. 2019. The Score of Students Solving Math Expression

  337. 2035. Partition Array Into Two Arrays to Minimize Sum Difference

  338. 2036. Maximum Alternating Subarray Sum

  339. 2050. Parallel Courses III

  340. 2052. Minimum Cost to Separate Sentence Into Rows

  341. 2054. Two Best Non-Overlapping Events

  342. 2060. Check if an Original String Exists Given Two Encoded Strings

  343. 2063. Vowels of All Substrings

  344. 2086. Minimum Number of Food Buckets to Feed the Hamsters

  345. 2088. Count Fertile Pyramids in a Land

  346. 2100. Find Good Days to Rob the Bank

  347. 2110. Number of Smooth Descent Periods of a Stock

  348. 2140. Solving Questions With Brainpower

  349. 2143. Choose Numbers From Two Arrays in Range

  350. 2147. Number of Ways to Divide a Long Corridor

  351. 2152. Minimum Number of Lines to Cover Points

  352. 2163. Minimum Difference in Sums After Removal of Elements

  353. 2167. Minimum Time to Remove All Cars Containing Illegal Goods

  354. 2172. Maximum AND Sum of Array

  355. 2184. Number of Ways to Build Sturdy Brick Wall

  356. 2188. Minimum Time to Finish the Race

  357. 2189. Number of Ways to Build House of Cards

  358. 2209. Minimum White Tiles After Covering With Carpets

  359. 2218. Maximum Value of K Coins From Piles

  360. 2222. Number of Ways to Select Buildings

  361. 2247. Maximum Cost of Trip With K Highways

  362. 2262. Total Appeal of A String

  363. 2263. Make Array Non-decreasing or Non-increasing

  364. 2266. Count Number of Texts

  365. 2267. Check if There Is a Valid Parentheses String Path

  366. 2272. Substring With Largest Variance

  367. 2291. Maximum Profit From Trading Stocks

  368. 2297. Jump Game VIII

  369. 2304. Minimum Path Cost in a Grid

  370. 2305. Fair Distribution of Cookies

  371. 2310. Sum of Numbers With Units Digit K

  372. 2311. Longest Binary Subsequence Less Than or Equal to K

  373. 2312. Selling Pieces of Wood

  374. 2313. Minimum Flips in Binary Tree to Get Result

  375. 2318. Number of Distinct Roll Sequences

  376. 2320. Count Number of Ways to Place Houses

  377. 2321. Maximum Score Of Spliced Array

  378. 2327. Number of People Aware of a Secret

  379. 2328. Number of Increasing Paths in a Grid

  380. 2338. Count the Number of Ideal Arrays

  381. 2355. Maximum Number of Books You Can Take

  382. 2361. Minimum Costs Using the Train Line

  383. 2369. Check if There is a Valid Partition For The Array

  384. 2370. Longest Ideal Subsequence

  385. 2376. Count Special Integers

  386. 2378. Choose Edges to Maximize Score in a Tree

  387. 2380. Time Needed to Rearrange a Binary String

  388. 2393. Count Strictly Increasing Subarrays

  389. 2400. Number of Ways to Reach a Position After Exactly k Steps

  390. 2403. Minimum Time to Kill All Monsters

  391. 2407. Longest Increasing Subsequence II

  392. 2420. Find All Good Indices

  393. 2430. Maximum Deletions on a String

  394. 2431. Maximize Total Tastiness of Purchased Fruits

  395. 2435. Paths in Matrix Whose Sum Is Divisible by K

  396. 2436. Minimum Split Into Subarrays With GCD Greater Than One

  397. 2439. Minimize Maximum of Array

  398. 2463. Minimum Total Distance Traveled

  399. 2464. Minimum Subarrays in a Valid Split

  400. 2466. Count Ways To Build Good Strings

  401. 2472. Maximum Number of Non-overlapping Palindrome Substrings

  402. 2478. Number of Beautiful Partitions

  403. 2484. Count Palindromic Subsequences

  404. 2495. Number of Subarrays Having Even Product

  405. 2501. Longest Square Streak in an Array

  406. 2510. Check if There is a Path With Equal Number of 0’s And 1’s

  407. 2518. Number of Great Partitions

  408. 2522. Partition String Into Substrings With Values at Most K

  409. 2533. Number of Good Binary Strings

  410. 2538. Difference Between Maximum and Minimum Price Sum

  411. 2547. Minimum Cost to Split an Array

  412. 2552. Count Increasing Quadruplets

  413. 2556. Disconnect Path in a Binary Matrix by at Most One Flip

  414. 2571. Minimum Operations to Reduce an Integer to 0

  415. 2572. Count the Number of Square-Free Subsets

  416. 2573. Find the String with LCP

  417. 2581. Count Number of Possible Root Nodes

  418. 2585. Number of Ways to Earn Points

  419. 2597. The Number of Beautiful Subsets

  420. 2606. Find the Substring With Maximum Cost

  421. 2617. Minimum Number of Visited Cells in a Grid

  422. 2638. Count the Number of K-Free Subsets

  423. 2645. Minimum Additions to Make Valid String

  424. 2646. Minimize the Total Price of the Trips

  425. 2673. Make Costs of Paths Equal in a Binary Tree

  426. 2681. Power of Heroes

  427. 2684. Maximum Number of Moves in a Grid

  428. 2707. Extra Characters in a String

  429. 2708. Maximum Strength of a Group

  430. 2712. Minimum Cost to Make All Characters Equal

  431. 2713. Maximum Strictly Increasing Cells in a Matrix

  432. 2719. Count of Integers

  433. 2741. Special Permutations

  434. 2742. Painting the Walls

  435. 2745. Construct the Longest New String

  436. 2746. Decremental String Concatenation

  437. 2750. Ways to Split Array Into Good Subarrays

  438. 2767. Partition String Into Minimum Beautiful Substrings

  439. 2770. Maximum Number of Jumps to Reach the Last Index

  440. 2771. Longest Non-decreasing Subarray From Two Arrays

  441. 2786. Visit Array Positions to Maximize Score

  442. 2787. Ways to Express an Integer as Sum of Powers

  443. 2791. Count Paths That Can Form a Palindrome in a Tree

  444. 2801. Count Stepping Numbers in Range

  445. 2809. Minimum Time to Make Array Sum At Most x

  446. 2811. Check if it is Possible to Split Array

  447. 2826. Sorting Three Groups

  448. 2827. Number of Beautiful Integers in the Range

  449. 2830. Maximize the Profit as the Salesman

  450. 2836. Maximize Value of Function in a Ball Passing Game

  451. 2850. Minimum Moves to Spread Stones Over Grid

  452. 2851. String Transformation

  453. 2858. Minimum Edge Reversals So Every Node Is Reachable

  454. 2867. Count Valid Paths in a Tree

  455. 2876. Count Visited Nodes in a Directed Graph

  456. 2892. Minimizing Array After Replacing Pairs With Their Product

  457. 2896. Apply Operations to Make Two Strings Equal

  458. 2900. Longest Unequal Adjacent Groups Subsequence I

  459. 2901. Longest Unequal Adjacent Groups Subsequence II

  460. 2902. Count of Sub-Multisets With Bounded Sum

  461. 2911. Minimum Changes to Make K Semi-palindromes

  462. 2912. Number of Ways to Reach Destination in the Grid

  463. 2915. Length of the Longest Subsequence That Sums to Target

  464. 2916. Subarrays Distinct Element Sum of Squares II

  465. 2919. Minimum Increment Operations to Make Array Beautiful

  466. 2920. Maximum Points After Collecting Coins From All Nodes

  467. 2925. Maximum Score After Applying Operations on a Tree

  468. 2926. Maximum Balanced Subsequence Sum

  469. 2930. Number of Strings Which Can Be Rearranged to Contain Substring

  470. 2944. Minimum Number of Coins for Fruits

  471. 2945. Find Maximum Non-decreasing Array Length

  472. 2957. Remove Adjacent Almost-Equal Characters

  473. 2969. Minimum Number of Coins for Fruits II

  474. 2973. Find Number of Coins to Place in Tree Nodes

  475. 2977. Minimum Cost to Convert String II

  476. 2979. Most Expensive Item That Can Not Be Bought

  477. 2992. Number of Self-Divisible Permutations

  478. 2998. Minimum Number of Operations to Make X and Y Equal

  479. 2999. Count the Number of Powerful Integers

  480. 3003. Maximize the Number of Partitions After Operations

  481. 3004. Maximum Subtree of the Same Color

  482. 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K

  483. 3018. Maximum Number of Removal Queries That Can Be Processed I

  484. 3032. Count Numbers With Unique Digits II

  485. 3040. Maximum Number of Operations With the Same Score II

  486. 3041. Maximize Consecutive Elements in an Array After Modification

  487. 3068. Find the Maximum Sum of Node Values

  488. 3077. Maximum Strength of K Disjoint Subarrays

  489. 3082. Find the Sum of the Power of All Subsequences

  490. 3098. Find the Sum of Subsequence Powers

  491. 3117. Minimum Sum of Values by Dividing Array

  492. 3122. Minimum Number of Operations to Satisfy Conditions

  493. 3129. Find All Possible Stable Binary Arrays I

  494. 3130. Find All Possible Stable Binary Arrays II

  495. 3135. Equalize Strings by Adding or Removing Characters at Ends

  496. 3144. Minimum Substring Partition of Equal Character Frequency

  497. 3148. Maximum Difference Score in a Grid

  498. 3149. Find the Minimum Cost Array Permutation

  499. 3154. Find Number of Ways to Reach the K-th Stair

  500. 3165. Maximum Sum of Subsequence With Non-adjacent Elements

  501. 3176. Find the Maximum Length of a Good Subsequence I

  502. 3177. Find the Maximum Length of a Good Subsequence II

  503. 3180. Maximum Total Reward Using Operations I

  504. 3181. Maximum Total Reward Using Operations II

  505. 3183. The Number of Ways to Make the Sum

  506. 3186. Maximum Total Damage With Spell Casting

  507. 3192. Minimum Operations to Make Binary Array Elements Equal to One II

  508. 3193. Count the Number of Inversions

  509. 3196. Maximize Total Cost of Alternating Subarrays

  510. 3201. Find the Maximum Length of Valid Subsequence I

  511. 3202. Find the Maximum Length of Valid Subsequence II

  512. 3205. Maximum Array Hopping Score I

  513. 3213. Construct String with Minimum Cost

  514. 3218. Minimum Cost for Cutting Cake I

  515. 3225. Maximum Score From Grid Operations

  516. 3229. Minimum Operations to Make Array Equal to Target

  517. 3241. Time Taken to Mark All Nodes

  518. 3247. Number of Subsequences with Odd Sum

  519. 3250. Find the Count of Monotonic Pairs I

  520. 3251. Find the Count of Monotonic Pairs II

  521. 3256. Maximum Value Sum by Placing Three Rooks I

  522. 3257. Maximum Value Sum by Placing Three Rooks II

  523. 3259. Maximum Energy Boost From Two Drinks

  524. 3260. Find the Largest Palindrome Divisible by K

  525. 3269. Constructing Two Increasing Arrays

  526. 3276. Select Cells in Grid With Maximum Score

  527. 3277. Maximum XOR Score Subarray Queries

  528. 3284. Sum of Consecutive Subarrays

  529. 3287. Find the Maximum Sequence Value of Array

  530. 3290. Maximum Multiplication Score

  531. 3291. Minimum Number of Valid Strings to Form Target I

  532. 3292. Minimum Number of Valid Strings to Form Target II

  533. 3299. Sum of Consecutive Subsequences

  534. 3302. Find the Lexicographically Smallest Valid Sequence

  535. 3316. Find Maximum Removals From Source String

  536. 3317. Find the Number of Possible Ways for an Event

  537. 3320. Count The Number of Winning Sequences

  538. 3332. Maximum Points Tourist Can Earn

  539. 3333. Find the Original Typed String II

  540. 3335. Total Characters in String After Transformations I

  541. 3336. Find the Number of Subsequences With Equal GCD

  542. 3337. Total Characters in String After Transformations II

  543. 3339. Find the Number of K-Even Arrays

  544. 3343. Count Number of Balanced Permutations

  545. 3351. Sum of Good Subsequences

  546. 3352. Count K-Reducible Numbers Less Than N

  547. 3363. Find the Maximum Number of Fruits Collected

  548. 3366. Minimum Array Sum

  549. 3367. Maximize Sum of Weights after Edge Removals

  550. 3376. Minimum Time to Break Locks I

  551. 3388. Count Beautiful Splits in an Array

  552. 3389. Minimum Operations to Make Character Frequencies Equal

  553. 3393. Count Paths With the Given XOR Value

  554. 3409. Longest Subsequence With Decreasing Adjacent Difference

  555. 3410. Maximize Subarray Sum After Removing All Occurrences of One Element

  556. 3414. Maximum Score of Non-overlapping Intervals

  557. 3418. Maximum Amount of Money Robot Can Earn

  558. 3428. Maximum and Minimum Sums of at Most Size K Subsequences

  559. 3429. Paint House IV

  560. 3434. Maximum Frequency After Subarray Operation

  561. 3441. Minimum Cost Good Caption

  562. 3444. Minimum Increments for Target Multiples in an Array

  563. 3448. Count Substrings Divisible By Last Digit

  564. 3458. Select K Disjoint Special Substrings

  565. 3459. Length of Longest V-Shaped Diagonal Segment

  566. 3466. Maximum Coin Collection

  567. 3469. Find Minimum Cost to Remove Array Elements

  568. 3472. Longest Palindromic Subsequence After at Most K Operations

  569. 3473. Sum of K Subarrays With Length at Least M

  570. 3489. Zero Array Transformation IV

  571. 3490. Count Beautiful Numbers

  572. 3500. Minimum Cost to Divide Array Into Subarrays

  573. 3503. Longest Palindrome After Substring Concatenation I

  574. 3504. Longest Palindrome After Substring Concatenation II

  575. 3505. Minimum Operations to Make Elements Within K Subarrays Equal

{image_attr}

2. 树形 DP 套路

树形 DP 套路使用前提：如果题目求解目标是 S 规则，则求解释流程可以定成以每一个节点为头节点的子树在 S 规则下的每一个答案，并且最终答案一定就在其中。

树形 DP 套路的解题步骤

  1. 第一步：以某个节点 X 为头节点的子树中，分析答案有哪些可能性，并且这种分析是以 X 的左子树、X 的右子树和 X 整棵树的角度来考虑可能性的。

    Tip
    		 请注意这里的顺序：左子树、右子树及整棵树。先左右，如果左右满足，则就可以先上延伸，判断出整棵树。这也是递归调用“触底反弹”的过程。所以，很容易使用递归来完成相关操作。根据上述的流程，使用 后序遍历 更合适。

  2. 第二步：根据第一步的可能性分析，列出所有需要的信息。比如：最大值、最小值，高度，深度，节点数等等。

  3. 第三步：合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构。

    Tip
    		 写出信息结构是把所有的信息都装到一个对象中。如果只需要一个信息，就可以用简单类型来表示了。但是，在树的结构中，大概率是需要多个信息的。

  4. 第四步：设计递归函数，递归函数是处理以 X 为头节点的情况下的大难，包括设计递归的 base case，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构。