Curated sets
Dynamic programming ladder
Every judgeable DP problem, easiest first.
Total results3,128 problems
| Topics | Judge | |||||
|---|---|---|---|---|---|---|
| GuitaristGiven a starting volume and a sequence of forced up/down changes bounded by [0, M], find the maximum achievable volume for the last song using reachability DP. | Medium4 | Dynamic programmingArray | No attempts yet | 2s | 128 MB | Judgeable |
| Building Completion TimesGiven N buildings with construction times and prerequisite dependencies, compute for each building the earliest possible completion time assuming unlimited parallel construction. | Medium4 | Topological sortDynamic programming+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Downhill PathsCount the number of strictly decreasing height paths from the top-left to the bottom-right cell of a grid, moving only to adjacent cells, using memoized DFS. | Medium4 | Dynamic programmingDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Document SearchGiven a document and a word, find the maximum number of non-overlapping occurrences of the word within the document. | Medium4 | String matchingGreedy+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Perfect Attendance AwardCount length-N attendance strings over O, L, A that have at most one L and no three consecutive A's, modulo 1,000,000. | Medium4 | Dynamic programmingString+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Number of RoadsCount right/up lattice paths from (0,0) to (N,M) on a grid where certain unit edges are blocked by construction. | Medium4 | Dynamic programmingMatrix+1 | No attempts yet | 2s | 16 MB | Judgeable |
| Sum of SquaresGiven N up to 100,000, find the minimum number of perfect squares that sum to N. | Medium4 | Dynamic programmingMath | No attempts yet | 2s | 128 MB | Judgeable |
| Parcel RoutingGiven a weighted graph, compute for every pair of hubs the next hub to visit on a shortest path using all-pairs shortest paths. | Medium4 | Shortest pathGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| WormholesGiven roads with positive weights and wormholes with negative weights, detect whether any negative cycle exists in the resulting directed graph using Bellman-Ford. | Medium4 | Shortest pathGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| JumpCount the number of paths from top-left to bottom-right of a grid where each cell's value fixes the exact jump distance right or down. | Medium4 | Dynamic programmingMatrix | No attempts yet | 1s | 128 MB | Judgeable |
| Largest SquareGiven a binary grid, find the area of the largest square consisting entirely of 1s using dynamic programming. | Medium4 | Dynamic programmingMatrix | No attempts yet | 1s | 128 MB | Judgeable |
| Gift ExchangeCompute the number of derangements of N items modulo 1,000,000,000. | Medium4 | Dynamic programmingMath+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Exercise RouteFind the minimum weight cycle in a directed graph with up to 400 vertices, essentially detecting the shortest cycle via all-pairs shortest paths. | Medium4 | Shortest pathGraph+1 | No attempts yet | 2s | 192 MB | Judgeable |
| LCS of Three StringsCompute the length of the longest common subsequence shared by three given strings using dynamic programming. | Medium4 | Dynamic programmingString | No attempts yet | 2s | 128 MB | Judgeable |
| Box NestingFind the length of the longest strictly increasing subsequence of box sizes given in order. | Medium4 | Dynamic programmingBinary search+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Decode CountCount the number of ways to decode a digit string into letters A-Z, modulo 1,000,000. | Medium4 | Dynamic programmingString | No attempts yet | 2s | 128 MB | Judgeable |
| Minimum Time to Complete TasksGiven tasks with durations and prerequisites forming a DAG (prerequisites always have smaller index), compute the minimum total time to finish all tasks using longest path via DP. | Medium4 | Dynamic programmingTopological sort+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Tiling a 3-by-N WallCount the number of ways to tile a 3-by-N wall using 2x1 dominoes, for N up to 30. | Medium4 | Dynamic programmingCombinatorics | No attempts yet | 2s | 128 MB | Judgeable |
| Kimchi DeliveryGiven N cities on a line and a starting point, find the order of visiting all cities minimizing the sum of arrival times. | Medium4 | GreedyDynamic programming+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Collecting JewelsGiven N values in a line, find the maximum sum of a single contiguous run of length at least M taken once. | Medium4 | Prefix sumDynamic programming+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Maximum Independent Set in a TreeGiven a weighted tree, compute a maximum weight independent set using tree DP and output the chosen vertices. | Medium4 | Dynamic programmingTree+1 | No attempts yet | 2s | 128 MB | Judgeable |
| String Alignment ScoreCompute the maximum scoring alignment of two strings using gap and mismatch/match scoring, which is a classic sequence alignment (edit distance style) DP. | Medium4 | Dynamic programmingString | No attempts yet | 2s | 128 MB | Judgeable |
| Coin 1Given n coin denominations, count the number of combinations (order irrelevant, unlimited supply) that sum exactly to k. | Medium4 | Dynamic programming | No attempts yet | 0.5s | 4 MB | Judgeable |
| Semiconductor DesignGiven a permutation of port connections, find the longest increasing subsequence to avoid crossing lines. | Medium4 | Dynamic programmingBinary search | No attempts yet | 2s | 128 MB | Judgeable |
| Word GridCount the number of paths in an HxW grid moving to 8-directional neighbors (cells reusable) that spell out a given word of length L. | Medium4 | Dynamic programmingMatrix+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Color WheelCount the ways to choose K non-adjacent colors from N colors arranged in a circle, modulo 1,000,000,003. | Medium4 | CombinatoricsMath+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Climbing StairsFind the maximum score reachable by climbing stairs one or two at a time without stepping on three consecutive stairs, ending on the last stair. | Medium4 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| Fire EnginesGiven sorted positions of pumps and fire engines on a line, assign each engine a distinct pump to minimize total distance connected. | Medium4 | GreedyDynamic programming+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Number CardsCount the ways to split a digit string into tokens each representing a valid card number from 1 to 34 (no leading zero issues implied). | Medium4 | Dynamic programmingString | No attempts yet | 1s | 128 MB | Judgeable |
| Marble GameCompute Grundy-style win/lose states for a two-pile subtraction game with three fixed move sizes and report the winner for five given starting positions. | Medium4 | Dynamic programmingGame theory+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Changing a Bill with CoinsCount the number of ways to make an exact target sum T using bounded quantities of k coin denominations. | Medium4 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| Balance ScaleGiven a set of weights, determine for each marble weight whether it can be balanced using weights placed on either pan (subset sums with +/- coefficients). | Medium4 | Dynamic programmingBrute force+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Toy AssemblyCompute how many units of each basic part are needed to build one finished toy given a DAG of assembly quantities. | Medium4 | GraphDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Stacking Colored PaperGiven N rectangles with allowed 90-degree rotation, find the longest chain where each sheet fits entirely inside the previous one. | Medium4 | Dynamic programmingSorting+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Maximum Product of a Contiguous SubsequenceGiven N decimal numbers between 0.0 and 9.9, find the contiguous subsequence with the maximum product and print it rounded to three decimals. | Medium4 | Dynamic programmingArray | No attempts yet | 1s | 128 MB | Judgeable |
| Maximum Number of Noncrossing Circle ChordsGiven up to 50 chords on 100 circle points with distinct endpoints, find the maximum subset of chords with no two crossing. | Medium4 | Dynamic programmingIntervals+1 | No attempts yet | 1s | 128 MB | Judgeable |
| LottoCount n-element increasing subsequences from 1..m where each next number is at least double the previous, using combinatorics or DP. | Medium4 | Dynamic programmingCombinatorics+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Apple Catching GameMove a fixed-size basket left or right along N cells to catch a sequence of falling apples with minimum total movement distance. | Medium4 | Dynamic programmingGreedy+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Bridging SignalsGiven a permutation of wire connections between two ports, find the longest increasing subsequence to maximize non-crossing signals. | Medium4 | Binary searchDynamic programming+1 | No attempts yet | 1s | 128 MB | Judgeable |
| String Expansion and DistanceCompute the minimum alignment cost between two strings using edit-distance style dynamic programming with character mismatch costs and a fixed gap penalty K. | Medium4 | Dynamic programmingString | No attempts yet | 1s | 128 MB | Judgeable |
| Board JumpCount distinct paths from top-left to bottom-right of an N×N grid where each cell's digit fixes the exact jump length right or down, using big-integer DP. | Medium4 | Dynamic programmingMatrix+1 | No attempts yet | 1s | 128 MB | Judgeable |
| The VowDetermine, for each word and up to length 50000, whether it can be split into a sequence of one or two letter chemical element symbols using DP. | Medium4 | Dynamic programmingString | No attempts yet | 1s | 128 MB | Judgeable |
| Piggy-BankGiven empty and full weights of a piggy bank and coin value/weight pairs, find the minimum possible total coin value achieving the exact weight difference, using unbounded knapsack. | Medium4 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| MatchsticksGiven a number of matchsticks, find the smallest and largest positive numbers (no leading zero) that can be formed using exactly that many matchsticks based on per-digit costs. | Medium4 | Dynamic programmingGreedy+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Rising TrendFor each test case, compute the length of the longest strictly increasing subsequence in a sequence of up to 100000 prices. | Medium4 | Dynamic programmingBinary search+1 | No attempts yet | 1s | 128 MB | Judgeable |
| TourGiven points sorted by x-coordinate, compute the shortest bitonic tour that goes strictly left-to-right then strictly right-to-left, using classic O(n^2) DP. | Medium4 | Dynamic programmingGeometry+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Common SubsequenceCompute the length of the longest common subsequence of two given strings for multiple test cases. | Medium4 | Dynamic programmingString | No attempts yet | 1s | 128 MB | Judgeable |
| Cash MachineGiven a cash target and limited counts of several bill denominations, find the maximum total not exceeding the target using a bounded-knapsack style search. | Medium4 | Dynamic programmingBrute force | No attempts yet | 1s | 128 MB | Judgeable |
| Expected AllowanceGiven n m-sided dice and a cutback k, compute the exact reduced fraction for the expected value of max(1, sum of dice - k). | Medium4 | Dynamic programmingMath+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Babs’ Box BoutiqueGiven up to 10 boxes, each orientable in 3 ways, find the largest subset that can be stacked with each base fitting inside the one below. | Medium4 | Dynamic programmingSorting+2 | No attempts yet | 1s | 128 MB | Judgeable |
| sqrt log sinPrecompute x_i for all i up to 10^6 using the given recurrence with floating point floors, then answer each query modulo 10^6. | Medium4 | Dynamic programmingMath+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Is Bigger Smarter?Given pairs of weight and IQ for up to 1000 elephants, find the largest subset whose weights strictly increase while IQs strictly decrease. | Medium4 | Dynamic programmingSorting | No attempts yet | 1s | 128 MB | Judgeable |
| Is the Kid in Green Zelda?Find the minimum total cost path from the top-left to the bottom-right cell of an N x N grid where each cell's value is paid when visited. | Medium4 | GraphShortest path+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Pascal's TravelsCount paths on an n by n digit board from top-left to bottom-right, where each square's digit sets the exact right or down step length. | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Robot NavigationFind the length of the shortest command program that walks a robot from start to destination with turns and moves, and count distinct shortest programs modulo m. | Medium4 | BFSGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Triangle GraphFind the minimum vertex-cost path from top-center to bottom-center in a layered 3-column DAG over N rows. | Medium4 | Dynamic programmingGraph | No attempts yet | 1s | 256 MB | Judgeable |
| DiscountsFor each product, given buy-B-get-F-free offers and query amounts, find the maximum saving in dollars for each quantity. | Medium4 | Dynamic programmingGreedy+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Exotic FoodsGiven a sequence of food values, choose a subset with no two chosen positions adjacent so the total value is as large as possible. | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Frodo SequenceGiven repeated values of n less than 2^31, print the n-th term of the sequence defined by Fro_n = Fro_{n-1} + Fro_{n-2} - Fro_{n-3}. | Medium4 | MathDynamic programming+2 | No attempts yet | 1s | 128 MB | Judgeable |
| TransportWith at most 20 items, choose a subset whose total weight is at most W and whose total value is as large as possible. | Medium4 | Brute forceBacktracking+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Coin CollectionA robot walks right or down only from the top-left to the bottom-right of a grid, and we want the most coins it can pick up along the way. | Medium4 | Dynamic programmingMatrix+2 | No attempts yet | 1s | 128 MB | Judgeable |
| PastaCount sequences of length N over three kinds where no kind appears three or more times in a row, with some positions fixed, modulo 10000. | Medium4 | Dynamic programmingImplementation | No attempts yet | 1s | 128 MB | Judgeable |
| Road ShopCount the number of ways to choose bead counts for n colors summing to r, with at least m beads of each color. | Medium4 | CombinatoricsMath+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Hexagonal TilesCount the sequences of increasing tile numbers from the start tile to tile N, where each move goes forward by 1 or 2. | Medium4 | Dynamic programmingCombinatorics+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Tile ExchangingFor each of N tiles, pick a new side length (or keep the old one) so the total area equals M, minimizing the sum of squared side-length changes. | Medium4 | Dynamic programmingMath | No attempts yet | 1s | 128 MB | Judgeable |
| Bessie's Weight ProblemGiven N haybale weights and a limit H, find the largest total weight at most H that can be formed by choosing each bale at most once. | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Cow PinballGiven a triangle of nail scores with R rows, find the maximum sum along a path from the top nail down to the last row, moving to one of the two adjacent nails below each step. | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Longest Contiguous SubsequenceGiven two integer sequences, find the length of the longest run of consecutive elements that appears in both. | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Strange Towers of HanoiCompute the minimum number of moves to transfer n disks (n at most 12) from tower A to tower D using four towers. | Medium4 | Dynamic programmingRecursion+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Dairy QueenCount the number of ways to make N cents using unlimited coins of the given C denominations, ignoring order. | Medium4 | Dynamic programmingCombinatorics+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Dining CowsGiven a sequence of 1s and 2s, find the minimum number of values to change so the sequence becomes nondecreasing. | Medium4 | Dynamic programmingPrefix sum+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Clear and Present DangerGiven a danger matrix and a required sequence of islands, find the minimum total danger of a walk that visits those islands in order, allowing detours through others. | Medium4 | GraphShortest path+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Cow Pie TreasuresGiven an R by C grid of coin counts, find the maximum sum collected moving right one column each step, changing row by at most one, starting at (1,1) and ending at (R,C). | Medium4 | Dynamic programmingMatrix | No attempts yet | 1s | 128 MB | Judgeable |
| Hungry CowsGiven a sequence of N cow brands, find the length of the longest strictly increasing subsequence in the given order. | Medium4 | Dynamic programmingBinary search+2 | No attempts yet | 1s | 128 MB | Judgeable |
| The Bale TowerGiven up to 20 bales with distinct widths and breadths, find the longest chain where each bale is strictly smaller than the one below it. | Medium4 | Dynamic programmingSorting+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Cow SolitaireGiven an N by N grid of cards with point values, find the maximum total score along a monotone path from the lower-left corner to the upper-right corner moving only right or up. | Medium4 | Dynamic programmingMatrix+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Optimal Array Multiplication SequenceGiven the dimensions of a chain of matrices, find the minimum number of scalar multiplications needed to compute their product. | Medium4 | Dynamic programmingMatrix+2 | No attempts yet | 1s | 128 MB | Judgeable |
| CompromiseFor each pair of word lists terminated by #, print the lexicographically smallest longest common subsequence of words. | Medium4 | Dynamic programmingString | No attempts yet | 1s | 128 MB | Judgeable |
| Keep on Truckin'Given fixed and added motel distances, count overnight stop sequences where each day covers between A and B km. | Medium4 | Dynamic programmingArray+1 | No attempts yet | 1s | 128 MB | Judgeable |
| WaterparkCount the number of distinct paths from point 1 to point n in a DAG where every edge goes from a lower to a higher numbered point. | Medium4 | Dynamic programmingGraph | No attempts yet | 1s | 128 MB | Judgeable |
| Bridge CrossingSplit a line of people into consecutive groups of at most M, where each group costs its slowest member's time, and minimize the total cost. | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| GolfGiven a target distance and up to 32 distinct club distances, find how many strokes give an exact sum, using unlimited repeats of each club. | Medium4 | Dynamic programmingGreedy+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Herb TreesPick trees to keep so that no two kept trees are adjacent, maximizing the sum of their berry counts. | Medium4 | Dynamic programming | No attempts yet | 1s | 1024 MB | Judgeable |
| BukazoidsGiven cell counts and a fixed number of single and double jumps, maximize collected bukazoids and output the lexicographically smallest optimal visit sequence. | Medium4 | Dynamic programmingGreedy+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Dart ChallengeFor each dartboard, count how many distinct total scores k darts can produce, where each dart misses or scores s_i, 2s_i, or 3s_i (no triple on the top area). | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Filthy RichGiven a grid of gold amounts, find the maximum sum along a path from the top-left to the bottom-right cell, moving only east, south, or south-east. | Medium4 | Dynamic programmingMatrix+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Holiday GiftsAssign one of two priced gifts to each node of a rooted tree so no two adjacent employees share a gift, minimizing total cost. | Medium4 | TreeDynamic programming+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Baking CakesGiven up to 40 cake baking times and 3 ovens, find the minimum time to bake all cakes. | Medium4 | Dynamic programmingGreedy+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Numbers With No Repeated DigitsGiven n up to one million, print the n-th positive integer whose decimal digits are all distinct. | Medium4 | Brute forceDynamic programming+1 | No attempts yet | 1s | 128 MB | Judgeable |
| IndomieEach of the N people ahead takes a uniformly random remaining item among rice, sugar, and Indomie (Indomie limited to S). Find the probability Indomie remains for Felix, as a percentage. | Medium4 | ProbabilityCombinatorics+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Longest Ordered SubsequenceGiven a sequence of N integers, find the length of the longest non-decreasing subsequence. | Medium4 | Dynamic programmingArray+2 | No attempts yet | 1s | 128 MB | Judgeable |
| HandshakesCount the matchings of a path with n vertices, then print the last digit of that count. | Medium4 | Dynamic programmingCombinatorics+1 | No attempts yet | 1s | 256 MB | Judgeable |
| LadderCount the ways to climb s rungs with steps of one or two and report each answer modulo 2^p for up to a million queries. | Medium4 | Dynamic programmingMath | No attempts yet | 1s | 128 MB | Judgeable |
| MatchesStarting from one match, fire spreads to each neighbor no taller than the burning match, and the task asks for the largest group that can burn. | Medium4 | Dynamic programmingArray | No attempts yet | 1s | 128 MB | Judgeable |
| MerchantFind the simple path, possibly empty, in a weighted tree whose edge weights sum to the largest value. | Medium4 | TreeDynamic programming+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Missile ProtectorSelect the most missiles that form a non-decreasing height sequence in arrival order. | Medium4 | Dynamic programmingBinary search | No attempts yet | 1s | 128 MB | Judgeable |
| CoinsCount the unordered combinations of up to 20 coin values that sum to the target amount M. | Medium4 | Dynamic programmingCombinatorics | No attempts yet | 1s | 128 MB | Judgeable |
| The Frobenius ProblemCount the integers up to 1,000,000 that are not nonnegative combinations of four given numbers and report the largest such integer. | Medium4 | Dynamic programmingNumber theory | No attempts yet | 1s | 128 MB | Judgeable |
| Job Scheduling by Open BiddingPick bids whose total seconds fit the available time so the total payment is as large as possible. | Medium4 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| Mixing WordsDecide whether the third word interleaves the first two words while keeping each word's letter order. | Medium4 | Dynamic programmingString | No attempts yet | 1s | 256 MB | Judgeable |