動的計画法

動的計画法は、同じ形の小さな問題の答えを組み合わせて全体の答えを作り、その答えを保存して同じ計算を繰り返さない手法です。難しいのは状態が何を表すかを決めることで、コード自体は短いことがよくあります。

20 章 465 問の、いちばん大きな問題集です。入門 DP とグリッド DP から始まり、ナップサック、LCS と LIS、分割 DP、状態機械 DP を経て、区間 DP、bit DP、桁 DP、木 DP、グラフ上の DP、ゲーム DP、確率 DP へと進みます。具体的な解の復元やジャンプゲームの変形といった特集もあります。再帰に慣れていて、DP を順序立てて最後まで練習したい人に向いています。

465 問レーティング 1262–312520 章

書斎を開く

誰かと一緒にこの問題集を進めたいなら、ログインして書斎を開いてみてください。ヒロインが一問ずつ出題してくれます。

一、入門 DP

§1.1 階段上り

問題	レーティング
70. Climbing Stairs	未評価
746. Min Cost Climbing Stairs	1500
3693. Climbing Stairs II	1560
377. Combination Sum IV	1600
2466. Count Ways to Build Good Strings	1694
2266. Count Number of Texts	1857

§1.2 House Robber（隣接しない選択）

問題	レーティング
198. House Robber	未評価
213. House Robber II	未評価
2320. Count Number of Ways to Place Houses	1608
740. Delete AND Earn	未評価
3186. Maximum Total Damage with Spell Casting	1841
2140. Solving Questions with Brainpower	1709

§1.3 Maximum Subarray Sum

問題	レーティング
53. Maximum Subarray	未評価
2606. Find the Substring with Maximum Cost	1422
1749. Maximum Absolute Sum of Any Subarray	1542
1191. K Concatenation Maximum Sum	1748
918. Maximum Sum Circular Subarray	1777
2321. Maximum Score of Spliced Array	1791
152. Maximum Product Subarray	未評価
1186. Maximum Subarray Sum with One Deletion	1799
3381. Maximum Subarray Sum with Length Divisible by K	1943

二、Grid DP

§2.1 基礎

問題	レーティング
64. Minimum Path Sum	未評価
62. Unique Paths	未評価
63. Unique Paths II	未評価
120. Triangle	未評価
3393. Count Paths with the Given XOR Value	1573
931. Minimum Falling Path Sum	1573
2684. Maximum Number of Moves in a Grid	1626
3603. Minimum Cost Path with Alternating Directions II	1639
2304. Minimum Path Cost in a Grid	1658
1289. Minimum Falling Path Sum II	1697
3418. Maximum Amount of Money Robot Can Earn	1798
3742. Maximum Path Score in a Grid	1804
1824. Minimum Sideway Jumps	1778

§2.2 発展

問題	レーティング
1594. Maximum Non Negative Product in a Matrix	1807
1301. Number of Paths with Max Score	1853
3665. Twisted Mirror Path Count	1883
2435. Paths in Matrix Whose Sum Is Divisible by K	1952
174. Dungeon Game	未評価
329. Longest Increasing Path in a Matrix	未評価
2328. Number of Increasing Paths in a Grid	2001
2267. Check If There Is a Valid Parentheses String Path	2085
1937. Maximum Number of Points with Cost	2106
3363. Find the Maximum Number of Fruits Collected	2200
1463. Cherry Pickup II	未評価
741. Cherry Pickup	未評価
3459. Length of Longest V Shaped Diagonal Segment	2337

三、Knapsack

§3.1 0-1 Knapsack

問題	レーティング
416. Partition Equal Subset Sum	未評価
494. Target Sum	未評価
2915. Length of the Longest Subsequence That Sums to Target	1659
2787. Ways to Express an Integer As Sum of Powers	1818
3180. Maximum Total Reward Using Operations I	1849
474. Ones AND Zeroes	未評価
3489. Zero Array Transformation IV	2068
3685. Subsequence Sum After Capping Elements	2073
1049. Last Stone Weight II	2092
1774. Closest Dessert Cost	未評価
879. Profitable Schemes	2204
3082. Find the Sum of the Power of All Subsequences	2242
956. Tallest Billboard	2381
2518. Number of Great Partitions	2415
2742. Painting the Walls	2425
3181. Maximum Total Reward Using Operations II	2688

§3.2 Unbounded Knapsack

問題	レーティング
322. Coin Change	未評価
518. Coin Change II	未評価
279. Perfect Squares	未評価
3592. Inverse Coin Change	1701
1449. Form Largest Integer with Digits That Add Up to Target	1927

§3.3 Bounded Knapsack（任意）任意

問題	レーティング
2585. Number of Ways to Earn Points	1910
3333. Find the Original Typed String II	2629
2902. Count of Sub Multisets with Bounded Sum	2759
3489. Zero Array Transformation IV	未評価

§3.4 Grouped Knapsack

問題	レーティング
1155. Number of Dice Rolls with Target Sum	1654
1981. Minimize the Difference Between Target AND Chosen Elements	2010
2218. Maximum Value of K Coins From Piles	2158

§3.5 Tree Knapsack（任意）任意

問題	レーティング
3562. Maximum Profit From Trading Stocks with Discounts	2458

四、典型的なLinear DP

§4.1 Longest Common Subsequence (LCS)

問題	レーティング
1143. Longest Common Subsequence	未評価
583. Delete Operation for Two Strings	未評価
712. Minimum Ascii Delete Sum for Two Strings	未評価
72. Edit Distance	未評価
1035. Uncrossed Lines	1806
1458. Max Dot Product of Two Subsequences	1824
718. Maximum Length of Repeated Subarray	未評価
3290. Maximum Multiplication Score	1692
115. Distinct Subsequences	未評価
3628. Maximum Number of Subsequences After One Inserting	1754
3316. Find Maximum Removals From Source String	2062
1639. Number of Ways to Form a Target String Given a Dictionary	2082
97. Interleaving String	未評価
1092. Shortest Common Supersequence	未評価
44. Wildcard Matching	未評価
10. Regular Expression Matching	未評価

§4.2 Longest Increasing Subsequence (LIS)

問題	レーティング
300. Longest Increasing Subsequence	未評価
334. Increasing Triplet Subsequence	未評価
2826. Sorting Three Groups	1721
1671. Minimum Number of Removals to Make Mountain Array	1913
1964. Find the Longest Valid Obstacle Course at Each Position	1933
2111. Minimum Operations to Make the Array K Increasing	1941
354. Russian Doll Envelopes	未評価
1626. Best Team with No Conflicts	2027
1691. Maximum Height by Stacking Cuboids	2172
960. Delete Columns to Make Sorted III	2247
2407. Longest Increasing Subsequence II	2280
673. Number of Longest Increasing Subsequence	未評価
1187. Make Array Strictly Increasing	2316
1713. Minimum Operations to Make a Subsequence	2351
3288. Length of the Longest Increasing Path	2450
368. Largest Divisible Subset	1800
2901. Longest Unequal Adjacent Groups Subsequence II	1899

五、Partition DP

§5.1 分割できるかの判定

問題	レーティング
2369. Check If There Is a Valid Partition for the Array	1780
139. Word Break	未評価

§5.2 最適な分割

問題	レーティング
132. Palindrome Partitioning II	未評価
2707. Extra Characters in a String	1736
3196. Maximize Total Cost of Alternating Subarrays	1847
2767. Partition String Into Minimum Beautiful Substrings	1865
91. Decode Ways	未評価
639. Decode Ways II	未評価
1043. Partition Array for Maximum Sum	1916
3144. Minimum Substring Partition of Equal Character Frequency	1917
1416. Restore the Array	1920
2472. Maximum Number of Non Overlapping Palindrome Substrings	2013
1105. Filling Bookcase Shelves	2014
2547. Minimum Cost to Split an Array	2020
3578. Count Partitions with Max Min Difference at Most K	2033
2430. Maximum Deletions on a String	2102
2463. Minimum Total Distance Traveled	2454
3579. Minimum Steps to Convert String with Operations	2493
3500. Minimum Cost to Divide Array Into Subarrays	2569
3441. Minimum Cost Good Caption	2765

§5.3 分割数に制約のある分割

問題	レーティング
813. Largest Sum of Averages	1937
3599. Partition Array to Minimize XOR	1955
1278. Palindrome Partitioning III	1979
1745. Palindrome Partitioning IV	未評価
1335. Minimum Difficulty of a Job Schedule	2035
1473. Paint House III	2056
2209. Minimum White Tiles After Covering with Carpets	2106
1478. Allocate Mailboxes	2190
3473. Sum of K Subarrays with Length at Least M	2274
1959. Minimum Total Space Wasted with K Resizing Operations	2310
2478. Number of Beautiful Partitions	2344
3538. Merge Operations for Minimum Travel Time	2461
3505. Minimum Operations to Make Elements Within K Subarrays Equal	2539
3077. Maximum Strength of K Disjoint Subarrays	2557
2911. Minimum Changes to Make K Semi Palindromes	2608

六、State Machine DP

§6.1 株の売買

問題	レーティング
121. Best Time to Buy AND Sell Stock	未評価
122. Best Time to Buy AND Sell Stock II	未評価
123. Best Time to Buy AND Sell Stock III	未評価
188. Best Time to Buy AND Sell Stock IV	未評価
3573. Best Time to Buy AND Sell Stock V	1777
309. Best Time to Buy AND Sell Stock with Cooldown	未評価
714. Best Time to Buy AND Sell Stock with Transaction Fee	未評価

§6.2 基礎

問題	レーティング
3259. Maximum Energy Boost From Two Drinks	1484
2222. Number of Ways to Select Buildings	1657
2708. Maximum Strength of a Group	未評価
1567. Maximum Length of Subarray with Positive Product	1710
2786. Visit Array Positions to Maximize Score	1733
1911. Maximum Alternating Subsequence Sum	1786
376. Wiggle Subsequence	未評価

§6.3 発展

問題	レーティング
3628. Maximum Number of Subsequences After One Inserting	1754
2771. Longest Non Decreasing Subarray From Two Arrays	1792
1186. Maximum Subarray Sum with One Deletion	1799
1594. Maximum Non Negative Product in a Matrix	1807
3738. Longest Non Decreasing Subarray After Replacing at Most One Element	1811
3196. Maximize Total Cost of Alternating Subarrays	1847
935. Knight Dialer	未評価
1537. Get the Maximum Score	1961
2919. Minimum Increment Operations to Make Array Beautiful	2031
801. Minimum Swaps to Make Sequences Increasing	2066
3434. Maximum Frequency After Subarray Operation	2094
1955. Count Number of Special Subsequences	2125
3068. Find the Maximum Sum of Node Values	2268
3640. Trionic Array II	2278
2272. Substring with Largest Variance	2516
3661. Maximum Walls Destroyed by Robots	2525
3743. Maximize Cyclic Partition Score	3125

七、その他のLinear DP

§7.1 一次元 DP

問題	レーティング
3147. Taking Maximum Energy From the Mystic Dungeon	1460
2944. Minimum Number of Coins for Fruits	1709
2140. Solving Questions with Brainpower	1709
983. Minimum Cost for Tickets	1786
368. Largest Divisible Subset	1800
2901. Longest Unequal Adjacent Groups Subsequence II	1899
650. 2 Keys Keyboard	2000
871. Minimum Number of Refueling Stops	2074
32. Longest Valid Parentheses	未評価
2167. Minimum Time to Remove All Cars Containing Illegal Goods	2219
2188. Minimum Time to Finish the Race	2315
2896. Apply Operations to Make Two Strings Equal	未評価
3389. Minimum Operations to Make Character Frequencies Equal	2940
2597. The Number of Beautiful Subsets	未評価

§7.2 交わらない区間

問題	レーティング
2830. Maximize the Profit As the Salesman	1851
2008. Maximum Earnings From Taxi	1872
2054. Two Best Non Overlapping Events	1883
1235. Maximum Profit in Job Scheduling	2023
1751. Maximum Number of Events That Can Be Attended II	2041
3414. Maximum Score of Non Overlapping Intervals	2723

§7.3 subarray DP

問題	レーティング
53. Maximum Subarray	未評価
152. Maximum Product Subarray	未評価
1186. Maximum Subarray Sum with One Deletion	1799
3738. Longest Non Decreasing Subarray After Replacing at Most One Element	1811
3524. Find X Value of Array I	2008
3448. Count Substrings Divisible by Last Digit	2387
2262. Total Appeal of a String	2033
828. Count Unique Characters of All Substrings of a Given String	2034
467. Unique Substrings in Wraparound String	未評価

§7.4 条件を満たすsubsequenceの DP

問題	レーティング
2501. Longest Square Streak in an Array	1480
1218. Longest Arithmetic Subsequence of Given Difference	1597
2826. Sorting Three Groups	1721
1027. Longest Arithmetic Subsequence	1759
2370. Longest Ideal Subsequence	1835
873. Length of Longest Fibonacci Subsequence	1911
3686. Number of Stable Subsequences	1969
3202. Find the Maximum Length of Valid Subsequence II	1974
446. Arithmetic Slices II Subsequence	未評価
3351. Sum of Good Subsequences	2086
3041. Maximize Consecutive Elements in an Array After Modification	2231
3409. Longest Subsequence with Decreasing Adjacent Difference	2500
3098. Find the Sum of Subsequence Powers	2553
2901. Longest Unequal Adjacent Groups Subsequence II	未評価
1048. Longest String Chain	1599
940. Distinct Subsequences II	1985
1987. Number of Unique Good Subsequences	2422
730. Count Different Palindromic Subsequences	未評価

§7.5 部分長方形 DP

問題	レーティング
3148. Maximum Difference Score in a Grid	1820
221. Maximal Square	未評価
1277. Count Square Submatrices with All Ones	未評価
2088. Count Fertile Pyramids in a Land	2105
3197. Find the Minimum Area to Cover All Ones II	未評価

§7.6 多次元 DP

問題	レーティング
2222. Number of Ways to Select Buildings	1657
2826. Sorting Three Groups	1721
2400. Number of Ways to Reach a Position After Exactly K Steps	1751
1262. Greatest Sum Divisible by Three	1762
3332. Maximum Points Tourist Can Earn	1828
3176. Find the Maximum Length of a Good Subsequence I	1849
1269. Number of Ways to Stay in the Same Place After Some Steps	1854
3250. Find the Count of Monotonic Pairs I	1898
3218. Minimum Cost for Cutting Cake I	未評価
3122. Minimum Number of Operations to Satisfy Conditions	1905
576. Out of Boundary Paths	未評価
403. Frog Jump	未評価
3725. Count Ways to Choose Coprime Integers From Rows	1982
1223. Dice Roll Simulation	2008
1320. Minimum Distance to Type a Word Using Two Fingers	2028
3366. Minimum Array Sum	2040
1575. Count All Possible Routes	2055
3154. Find Number of Ways to Reach the K Th Stair	2071
2318. Number of Distinct Roll Sequences	2090
3469. Find Minimum Cost to Remove Array Elements	2112
2746. Decremental String Concatenation	2126
1444. Number of Ways of Cutting a Pizza	2127
3320. Count the Number of Winning Sequences	2153
3429. Paint House IV	2166
2896. Apply Operations to Make Two Strings Equal	2172
1420. Build Array Where You Can Find the Maximum Exactly K Comparisons	2176
3193. Count the Number of Inversions	2266
1079. Letter Tile Possibilities	未評価
1866. Number of Ways to Rearrange Sticks with K Sticks Visible	2333
2312. Selling Pieces of Wood	2363
3177. Find the Maximum Length of a Good Subsequence II	2365
1884. Egg Drop with 2 Eggs AND N Floors	未評価
887. Super Egg Drop	2377
920. Number of Music Playlists	2400
3336. Find the Number of Subsequences with Equal Gcd	2403
1388. Pizza with 3n Slices	2410
903. Valid Permutations for Di Sequence	2433
1900. The Earliest AND Latest Rounds Where Players Compete	2455
1531. String Compression II	2576
1883. Minimum Skips to Arrive at Meeting on Time	2588
964. Least Operators to Express Number	2594
3343. Count Number of Balanced Permutations	2615
1787. Make the XOR of All Segments Equal to Zero	2640
3509. Maximum Product of Subsequences with an Alternating Sum Equal to K	2703
3441. Minimum Cost Good Caption	2765
3539. Find Sum of Array Product of Magical Sequences	2694
2060. Check If an Original String Exists Given Two Encoded Strings	2804
2809. Minimum Time to Make Array Sum at Most X	2979
3003. Maximize the Number of Partitions After Operations	3039
3225. Maximum Score From Grid Operations	3028

八、Interval DP

§8.1 最長回文subsequence

問題	レーティング
516. Longest Palindromic Subsequence	未評価
1312. Minimum Insertion Steps to Make a String Palindrome	1787
3472. Longest Palindromic Subsequence After at Most K Operations	1884
1771. Maximize Palindrome Length From Subsequences	2182
730. Count Different Palindromic Subsequences	未評価

§8.2 Interval DP

問題	レーティング
5. Longest Palindromic Substring	未評価
647. Palindromic Substrings	未評価
3040. Maximum Number of Operations with the Same Score II	1709
375. Guess Number Higher OR Lower II	未評価
1130. Minimum Cost Tree From Leaf Values	1919
96. Unique Binary Search Trees	未評価
1770. Maximum Score From Performing Multiplication Operations	2068
1547. Minimum Cost to Cut a Stick	2116
1039. Minimum Score Triangulation of Polygon	2130
1000. Minimum Cost to Merge Stones	2423
2019. The Score of Students Solving Math Expression	2584
3563. Lexicographically Smallest String After Adjacent Removals	2585
3277. Maximum XOR Score Subarray Queries	2693
87. Scramble String	未評価
312. Burst Balloons	未評価
664. Strange Printer	未評価
546. Remove Boxes	未評価

九、Bitmask DP

§9.1 順列型 Bitmask DP ① 隣接に依存しない

問題	レーティング
526. Beautiful Arrangement	未評価
1799. Maximize Score After N Operations	未評価
3533. Concatenated Divisibility	2257
3530. Maximum Profit From Valid Topological Order in Dag	2353

§9.2 順列型 Bitmask DP ② 隣接に依存する

問題	レーティング
2741. Special Permutations	2021
996. Number of Squareful Arrays	未評価
1681. Minimum Incompatibility	2390
3615. Longest Palindromic Path in Graph	2463
3283. Maximum Number of Moves to Kill All Pawns	2473
3149. Find the Minimum Cost Array Permutation	2642

§9.3 巡回セールスマン問題（TSP）

問題	レーティング
943. Find the Shortest Superstring	2186

§9.4 部分集合 Bitmask DP

問題	レーティング
2305. Fair Distribution of Cookies	1887
1986. Minimum Number of Work Sessions to Finish the Tasks	1995
3670. Maximum Product of Two Integers with No Common Bits	2234
1723. Find Minimum Time to Finish All Jobs	2284
1655. Distribute Repeating Integers	2307
3444. Minimum Increments for Target Multiples in an Array	2337
3575. Maximum Good Subtree Score	2360
1681. Minimum Incompatibility	2390
2572. Count the Number of Square Free Subsets	2420
1994. The Number of Good Subsets	2465
1494. Parallel Courses II	未評価

§9.5 輪郭線 DP（Broken Profile）

問題	レーティング
1411. Number of Ways to Paint N 3 Grid	1845
1931. Painting a Grid with Three Different Colors	2170
1659. Maximize Grid Happiness	2655
980. Unique Paths III	未評価

§9.6 SOS DP（高速ゼータ変換）

問題	レーティング
3670. Maximum Product of Two Integers with No Common Bits	2234
2044. Count Number of Maximum Bitwise OR Subsets	未評価
2732. Find a Good Subset of the Matrix	未評価
3757. Number of Effective Subsequences	2519

§9.7 その他の Bitmask DP

問題	レーティング
473. Matchsticks to Square	未評価
698. Partition to K Equal Sum Subsets	未評価
2002. Maximum Product of the Length of Two Palindromic Subsequences	1869
1125. Smallest Sufficient Team	2251
1434. Number of Ways to Wear Different Hats to Each Other	2273
464. Can I Win	未評価
691. Stickers to Spell Word	未評価
1815. Maximum Number of Groups Getting Fresh Donuts	2559

十、Digit DP

§10.1 条件を満たす要素の個数を数える

問題	レーティング
3747. Count Distinct Integers After Removing Zeros	1848
2719. Count of Integers	未評価
1399. Count Largest Group	未評価
1742. Maximum Number of Balls in a Box	未評価
788. Rotated Digits	未評価
902. Numbers at Most N Given Digit Set	1990
600. Non Negative Integers Without Consecutive Ones	未評価
2376. Count Special Integers	2120
357. Count Numbers with Unique Digits	未評価
1012. Numbers with Repeated Digits	2230
3519. Count Numbers with Non Decreasing Digits	2246
2827. Number of Beautiful Integers in the Range	2324
2999. Count the Number of Powerful Integers	2351
2801. Count Stepping Numbers in Range	2367
2843. Count Symmetric Integers	未評価
3352. Count K Reducible Numbers Less Than N	2451
3621. Number of Integers with Popcount Depth Equal to K I	未評価
3490. Count Beautiful Numbers	2502
1397. Find All Good Strings	2667

§10.2 条件を満たす要素の値の総和を求める

問題	レーティング
233. Number of Digit One	未評価
3753. Total Waviness of Numbers in Range II	2297

§10.3 その他のDigit DP

問題	レーティング
3677. Count Binary Palindromic Numbers	2223
3348. Smallest Divisible Digit Product II	3101

十一、DP の高速化

§11.1 Prefix Sumによる DP の高速化

問題	レーティング
1871. Jump Game VII	1896
2327. Number of People Aware of a Secret	未評価
3699. Number of Zigzag Arrays I	2123
1997. First Day Where You Have Been in All the Rooms	2260
629. K Inverse Pairs Array	未評価
3193. Count the Number of Inversions	2266
3473. Sum of K Subarrays with Length at Least M	2274
3251. Find the Count of Monotonic Pairs II	2323
2478. Number of Beautiful Partitions	2344
837. New 21 Game	2350
3077. Maximum Strength of K Disjoint Subarrays	2557
3333. Find the Original Typed String II	2629
2902. Count of Sub Multisets with Bounded Sum	2759
1977. Number of Ways to Separate Numbers	2817
3130. Find All Possible Stable Binary Arrays II	2825

§11.2 Monotonic Stackによる DP の高速化

問題	レーティング
1335. Minimum Difficulty of a Job Schedule	2035
2866. Beautiful Towers II	2072
2617. Minimum Number of Visited Cells in a Grid	2582

§11.3 Monotonic Queueによる DP の高速化

問題	レーティング
2944. Minimum Number of Coins for Fruits	1709
1696. Jump Game VI	1954
1425. Constrained Subsequence Sum	2032
3578. Count Partitions with Max Min Difference at Most K	2033
375. Guess Number Higher OR Lower II	未評価
1687. Delivering Boxes From Storage to Ports	2610
2463. Minimum Total Distance Traveled	未評価
2945. Find Maximum Non Decreasing Array Length	2943

§11.4 BIT / Segment Treeによる DP の高速化

問題	レーティング
1626. Best Team with No Conflicts	2027
2407. Longest Increasing Subsequence II	2280
2770. Maximum Number of Jumps to Reach the Last Index	未評価
2926. Maximum Balanced Subsequence Sum	2448
2547. Minimum Cost to Split an Array	未評価
3671. Sum of Beautiful Subsequences	2647
2916. Subarrays Distinct Element Sum of Squares II	2816

§11.5 Trieによる DP の高速化

問題	レーティング
139. Word Break	未評価
2707. Extra Characters in a String	未評価
472. Concatenated Words	2300

§11.6 行列累乗による DP の高速化

問題	レーティング
70. Climbing Stairs	未評価
509. Fibonacci Number	未評価
1137. N Th Tribonacci Number	未評価
1220. Count Vowels Permutation	未評価
552. Student Attendance Record II	未評価
935. Knight Dialer	未評価
790. Domino AND Tromino Tiling	未評価
1411. Number of Ways to Paint N 3 Grid	未評価
1931. Painting a Grid with Three Different Colors	未評価
3337. Total Characters in String After Transformations II	2412
3700. Number of Zigzag Arrays II	2435
2851. String Transformation	2858

§11.7 Convex Hull Trick（傾き最適化）

問題	レーティング
3494. Find the Minimum Amount of Time to Brew Potions	未評価
3500. Minimum Cost to Divide Array Into Subarrays	未評価
3693. Climbing Stairs II	未評価

§11.8 Alien DP（WQS 二分）

問題	レーティング
188. Best Time to Buy AND Sell Stock IV	未評価
3573. Best Time to Buy AND Sell Stock V	未評価
2209. Minimum White Tiles After Covering with Carpets	未評価
3743. Maximize Cyclic Partition Score	未評価

§11.9 その他の DP 高速化

問題	レーティング
3654. Minimum Sum After Divisible Sum Deletions	2039
1937. Maximum Number of Points with Cost	2106
2713. Maximum Strictly Increasing Cells in a Matrix	2387
3651. Minimum Cost Path with Teleportations	2411
2318. Number of Distinct Roll Sequences	未評価
3181. Maximum Total Reward Using Operations II	2688
2267. Check If There Is a Valid Parentheses String Path	未評価
3213. Construct String with Minimum Cost	未評価
3292. Minimum Number of Valid Strings to Form Target II	未評価
3743. Maximize Cyclic Partition Score	未評価

十二、Tree DP

§12.1 木の直径

問題	レーティング
543. Diameter of Binary Tree	未評価
687. Longest Univalue Path	未評価
124. Binary Tree Maximum Path Sum	未評価
2385. Amount of Time for Binary Tree to Be Infected	1711
2246. Longest Path with Different Adjacent Characters	2126
3203. Find Minimum Diameter After Merging Two Trees	2266
1617. Count Subtrees with Max Distance Between Cities	2309
2538. Difference Between Maximum AND Minimum Price Sum	2398
3372. Maximize the Number of Target Nodes After Connecting Trees I	未評価

§12.2 木の最大独立集合

問題	レーティング
337. House Robber III	未評価
2646. Minimize the Total Price of the Trips	2238
3544. Subtree Inversion Sum	2545

§12.3 木の最小支配集合

問題	レーティング
968. Binary Tree Cameras	2124

§12.4 Rerooting Tree DP

問題	レーティング
834. Sum of Distances in Tree	2197
2581. Count Number of Possible Root Nodes	2228
2858. Minimum Edge Reversals So Every Node Is Reachable	2295
310. Minimum Height Trees	未評価
3241. Time Taken to Mark All Nodes	2522
3372. Maximize the Number of Target Nodes After Connecting Trees I	未評価

§12.5 その他のTree DP

問題	レーティング
2925. Maximum Score After Applying Operations on a Tree	1940
3068. Find the Maximum Sum of Node Values	2268
2920. Maximum Points After Collecting Coins From All Nodes	2351
3575. Maximum Good Subtree Score	2360
3562. Maximum Profit From Trading Stocks with Discounts	2458
1916. Count Ways to Build Rooms in an Ant Colony	2486
3367. Maximize Sum of Weights After Edge Removals	2602

十三、グラフ上の DP

問題	レーティング
3543. Maximum Weighted K Edge Path	2110
913. Cat AND Mouse	2800
1728. Cat AND Mouse II	2849

十四、Game Theory DP

問題	レーティング
1025. Divisor Game	1435
877. Stone Game	1590
486. Predict the Winner	未評価
1510. Stone Game IV	1787
1690. Stone Game VII	1951
1406. Stone Game III	2027
1140. Stone Game II	2035
1563. Stone Game V	2087
464. Can I Win	未評価
1872. Stone Game VIII	2440
913. Cat AND Mouse	2800
1728. Cat AND Mouse II	2849

十五、確率・期待値DP

問題	レーティング
688. Knight Probability in Chessboard	未評価
837. New 21 Game	2350
1467. Probability of a Two Boxes Having the Same Number of Distinct Balls	2357
808. Soup Servings	2397

特集：具体的な解の復元（解の出力）

問題	レーティング
368. Largest Divisible Subset	未評価
1363. Largest Multiple of Three	1823
1449. Form Largest Integer with Digits That Add Up to Target	1927
1092. Shortest Common Supersequence	1977
943. Find the Shortest Superstring	2186
1125. Smallest Sufficient Team	2251
3533. Concatenated Divisibility	2257
3260. Find the Largest Palindrome Divisible by K	2370
3149. Find the Minimum Cost Array Permutation	2642
3441. Minimum Cost Good Caption	2765
3348. Smallest Divisible Digit Product II	3101

特集：前後からの分解

問題	レーティング
724. Find Pivot Index	未評価
1991. Find the Middle Index in Array	未評価
3707. Equal Score Substrings	1262
2270. Number of Ways to Split Array	1334
2256. Minimum Average Difference	1395
1422. Maximum Score After Splitting a String	未評価
238. Product of Array Except Self	未評価
1493. Longest Subarray of 1s After Deleting One Element	1423
845. Longest Mountain in Array	1437
2012. Sum of Beauty in the Array	1468
2909. Minimum Sum of Mountain Triplets II	1479
2483. Minimum Penalty for a Shop	1495
1525. Number of Good Ways to Split a String	1500
3583. Count Special Triplets	1510
3354. Make Array Elements Equal to Zero	未評価
1930. Unique Length 3 Palindromic Subsequences	1533
2874. Maximum Value of an Ordered Triplet II	1583
1664. Ways to Make a Fair Array	1590
123. Best Time to Buy AND Sell Stock III	未評価
3698. Split Array with Minimum Difference	1649
3598. Longest Common Prefix Between Adjacent Strings After Removals	1655
2222. Number of Ways to Select Buildings	1657
1031. Maximum Sum of Two Non Overlapping Subarrays	1680
689. Maximum Sum of 3 Non Overlapping Subarrays	未評価
2420. Find All Good Indices	1695
2100. Find Good Days to Rob the Bank	1702
926. Flip String to Monotone Increasing	未評価
334. Increasing Triplet Subsequence	未評価
1653. Minimum Deletions to Make String Balanced	1794
1186. Maximum Subarray Sum with One Deletion	1799
3738. Longest Non Decreasing Subarray After Replacing at Most One Element	1811
42. Trapping Rain Water	未評価
2711. Difference of Number of Distinct Values on Diagonals	未評価
1477. Find Two Non Overlapping Sub Arrays Each with Target Sum	1851
1671. Minimum Number of Removals to Make Mountain Array	1913
2906. Construct Product Matrix	2075
3334. Find the Maximum Factor Score of Array	未評価
2167. Minimum Time to Remove All Cars Containing Illegal Goods	2219
2484. Count Palindromic Subsequences	2223
2163. Minimum Difference in Sums After Removal of Elements	2225
2565. Subsequence with the Minimum Score	2432
1995. Count Special Quadruplets	未評価
2552. Count Increasing Quadruplets	2433
3302. Find the Lexicographically Smallest Valid Sequence	2474
3404. Count Special Subsequences	2445
3303. Find the Occurrence of First Almost Equal Substring	2509
3410. Maximize Subarray Sum After Removing All Occurrences of One Element	2844
3003. Maximize the Number of Partitions After Operations	3039

特集：X を Y に変える

問題	レーティング
397. Integer Replacement	未評価
2998. Minimum Number of Operations to Make X AND Y Equal	1795
2059. Minimum Operations to Convert Number	1850
991. Broken Calculator	1909
1553. Minimum Number of Days to Eat N Oranges	2048

特集：ジャンプゲーム

問題	レーティング
2770. Maximum Number of Jumps to Reach the Last Index	1533
403. Frog Jump	未評価
1340. Jump Game V	1866
1871. Jump Game VII	1896
1696. Jump Game VI	1954
975. Odd Even Jump	2079
1654. Minimum Jumps to Reach Home	2124

その他

雑多な問題

問題	レーティング
1387. Sort Integers by the Power Value	1507
823. Binary Trees with Factors	1900
756. Pyramid Transition Matrix	1990
2930. Number of Strings Which Can Be Rearranged to Contain Substring	2227
1896. Minimum Cost to Change the Final Value of Expression	2532

トラック 2 の 3 番目です。個数制限付きナップサックと木上のナップサックの 2 セクションは任意として発展編に回されるので、ルートは主要な章をそのまま進みます。

レーティングは zerotrac さんによる LeetCode コンテストレーティングです。zerotrac のレーティングがない問題は「未評価」と表示されます。

書斎を開く