Curated sets
Dynamic programming ladder
Every judgeable DP problem, easiest first.
Total results3,128 problems
| Topics | Judge | |||||
|---|---|---|---|---|---|---|
| The nth Fibonacci NumberGiven n up to 20, compute the nth Fibonacci number defined from 0 and 1. | Easy1 | Dynamic programmingRecursion | No attempts yet | 1s | 256 MB | Judgeable |
| Fibonacci Number 2Compute the nth Fibonacci number for n up to 90. | Easy2 | Dynamic programmingMath | No attempts yet | 1s | 128 MB | Judgeable |
| Fibonacci-like SequenceGiven n up to 116, compute the n-th term of the recurrence f(n) = f(n-1) + f(n-3) with f(1)=f(2)=f(3)=1. | Easy2 | Dynamic programmingMath+1 | No attempts yet | 2s | 512 MB | Judgeable |
| RGB StreetGiven per-house costs for three colors, compute the minimum total cost to paint all houses in a line so that no two adjacent houses share a color. | Easy3 | Dynamic programmingArray | No attempts yet | 0.5s | 128 MB | Judgeable |
| Make It OneCompute the minimum number of divide-by-3, divide-by-2, or subtract-1 operations needed to reduce N to 1. | Easy3 | Dynamic programmingMath | No attempts yet | 0.15s | 128 MB | Judgeable |
| GreetingGiven health costs and joy values for up to 20 people, pick a subset maximizing total joy while keeping total health loss below 100. | Easy3 | Dynamic programming | No attempts yet | 2s | 128 MB | Judgeable |
| 01 TilesCount length-N binary strings tileable by '1' and '00' pieces, modulo 15746, which reduces to a Fibonacci recurrence. | Easy3 | Dynamic programmingMath | No attempts yet | 0.75s | 256 MB | Judgeable |
| Maximum Subarray SumGiven up to 100,000 integers, compute the maximum sum of a non-empty contiguous subarray. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 128 MB | Judgeable |
| Integer TriangleGiven a triangle of up to 500 rows, compute the maximum sum path from top to bottom moving diagonally at each step. | Easy3 | Dynamic programmingMatrix | No attempts yet | 2s | 128 MB | Judgeable |
| OvertakingGiven entry and exit orders of N cars, count how many cars are not part of the longest common subsequence, meaning they overtook someone. | Easy3 | Dynamic programmingArray+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Downward GameGiven an N x 3 grid with limited column transitions between rows, compute the maximum and minimum total path sums from top to bottom. | Easy3 | Dynamic programmingMatrix | No attempts yet | 1s | 4 MB | Judgeable |
| Pinary NumbersCount binary strings of length N that start with 1 and have no two consecutive 1s, using Fibonacci-style counting with big integers up to N=90. | Easy3 | Dynamic programmingMath+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Sum DecompositionCount ordered sequences of K integers from 0 to N whose sum equals N, modulo 1,000,000,000. | Easy3 | Dynamic programmingCombinatorics+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Minimum Coin CountGiven n coin denominations, compute the minimum number of coins (unlimited supply) that sum to exactly k, or -1 if impossible. | Easy3 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| CombinationGiven n and m within 100, compute the exact value of the binomial coefficient C(n, m). | Easy3 | MathCombinatorics+1 | No attempts yet | 2s | 128 MB | Judgeable |
| SequenceFind the maximum length of a contiguous subarray of digits that is either nondecreasing or nonincreasing. | Easy3 | ArrayDynamic programming+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Line UpFind the minimum number of children to move so the line ends in sorted order, equivalent to N minus the longest increasing subsequence length. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 128 MB | Judgeable |
| Apartment ResidentsCompute the resident count in room n on floor k, defined by repeated prefix sums starting from room i having i residents on floor 0. | Easy3 | Dynamic programmingMath+1 | No attempts yet | 0.5s | 128 MB | Judgeable |
| Keypad PasswordsCount length-N digit sequences on a phone keypad where consecutive digits must be adjacent keys, modulo 1,234,567, for up to N=1000. | Easy3 | Dynamic programmingGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Counting Coin CombinationsCount the number of ways to sum a set of coin denominations (unlimited use, order ignored) to reach a target amount, for multiple test cases. | Easy3 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| DollarsSimulate converting between dollars and marks daily using given rates to maximize final dollar amount, truncated to two decimals. | Easy3 | GreedySimulation+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Towers of CoinsGiven move options 1, K, or L coins in a Nim-like turn game, determine for each pile size whether the first player wins under optimal play. | Easy3 | Dynamic programmingGame theory | No attempts yet | 1s | 128 MB | Judgeable |
| ProfitGiven a sequence of daily profits, find the maximum total over any non-empty stretch of consecutive days, across several test cases. | Easy3 | ArrayDynamic programming+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Fibonacci NumberGiven n, print the n-th Fibonacci number, where the sequence starts 1, 1 and each later term is the sum of the previous two. | Easy3 | Dynamic programmingMath+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Exact ChangeGiven a price and a multiset of up to 100 coin values, pick a subset summing to at least the price; minimize the sum first, then the number of coins. | Easy3 | Dynamic programmingArray+1 | No attempts yet | 1s | 128 MB | Judgeable |
| SkylineWe have N trapezoidal buildings listed from nearest to farthest. For each building, we must compute the fraction of its area that remains visible, i.e., the part of the trapezoid not hidden by any closer building. The presence of overlapping sloped roofs makes the computation nontrivial: for a given building we need to determine, for each horizontal coordinate, the maximum roof height among all closer buildings. Then the visible area is the integral, over the building’s own range [x1, x2], of the positive part of the difference between the building's top edge (roof) and that maximum height.For | Easy3 | GeometryIntervals+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Toxic AssetsGiven current values of basic investments and acyclic derivative definitions, compute the current worth of a portfolio made of these investments. | Easy3 | Dynamic programmingMath+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Coin RowGiven rows of coin values, pick non-adjacent coins to maximize the total collected in each row. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 128 MB | Judgeable |
| Commute RouteCount monotone east/north lattice paths from (1,1) to (a,b) that avoid n blocked intersections, with a and b at most 16. | Easy3 | Dynamic programmingCombinatorics+2 | No attempts yet | 1s | 128 MB | Judgeable |
| ProfitsGiven a sequence of N daily profits, find the maximum sum over any contiguous stretch of days. | Easy3 | ArrayDynamic programming+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Eating TogetherGiven a sequence of values from 1 to 3, find the fewest card changes so the sequence becomes non-decreasing or non-increasing. | Easy3 | ImplementationBrute force+1 | No attempts yet | 1s | 128 MB | Judgeable |
| World Cup NoiseFor each n below 45, count the n-bit strings that contain no two adjacent 1s, and print the result per scenario with a blank line between cases. | Easy3 | Dynamic programmingCombinatorics+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Making ChangeGiven a target amount and up to 10 coin denominations, find the fewest coins that sum exactly to the target. | Easy3 | Dynamic programmingGreedy+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Four QuartersFor each round count from 1 to 20, compute the probability that A wins, B wins, or the game ties after that many rounds of this four-coin game. | Easy3 | ProbabilityDynamic programming+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Mouse JourneyCount monotone right/down paths on an R by C grid from (1,1) to (R,C) that avoid K blocked cat cells. | Easy3 | Dynamic programmingMatrix+1 | No attempts yet | 2s | 512 MB | Judgeable |
| ElevatorRusnė goes from floor 0 to floor N using the elevator for at most K segments; minimize the total height of the segments she climbs on foot. | Easy3 | GreedySorting+1 | No attempts yet | 1s | 1024 MB | Judgeable |
| Prehistoric Operating SystemsCount binary strings of length n with no two adjacent D's, where D means DOORS and O means any other brand, for up to 40 test values of n. | Easy3 | Dynamic programmingCombinatorics+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Board GameStarting on field 1, move forward 1 to 6 fields per step to reach field n while collecting the largest possible sum of visited values. | Easy3 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| The Score ChartGiven a sequence of 0s, 1s, and 2s, find the length of the longest subsequence that never decreases. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 128 MB | Judgeable |
| EncodingCount binary strings of length n that start with 1 and contain no adjacent ones for up to 100 queries. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 1s | 128 MB | Judgeable |
| Adding 1, 2, and 3Count the ordered ways to write n as a sum of 1, 2, and 3 for each test case with n below 11. | Easy3 | Dynamic programming | No attempts yet | 1s | 512 MB | Judgeable |
| Function run funCompute the recursive function w(a, b, c) with memoization for each query line until -1 -1 -1. | Easy3 | Dynamic programmingRecursion | No attempts yet | 1s | 128 MB | Judgeable |
| Taxi RoutesCount the routes from the southwest to the northeast corner of a grid up to 30 by 30 that move only east or north and avoid blocked intersections. | Easy3 | Dynamic programmingMatrix | No attempts yet | 1s | 128 MB | Judgeable |
| FundraisedChoose unlimited units of N item kinds within budget X to maximize total importance. | Easy3 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| Padovan SequenceFor each test case, compute the Nth Padovan number defined by the spiral of equilateral triangles. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 128 MB | Judgeable |
| Generations of TribblesCompute the nth term of a four-term Fibonacci-like recurrence for up to 68 test cases with precomputation. | Easy3 | Dynamic programming | No attempts yet | 2s | 128 MB | Judgeable |
| Equal Sum SetsCount subsets of {1..n} with exactly k elements that sum to s for each dataset. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 3s | 128 MB | Judgeable |
| BABBAStarting from A and rewriting each B as BA and each A as B, count the As and Bs after K presses. | Easy3 | Dynamic programmingMath | No attempts yet | 1s | 128 MB | Judgeable |
| Stone GameTwo players alternately take 1 or 3 stones from a pile of N, and the program names the winner under perfect play. | Easy3 | Dynamic programmingGame theory | No attempts yet | 1s | 128 MB | Judgeable |
| Stone Game 2Two players alternately take 1 or 3 stones from a pile of N and the player taking the last stone loses, so print whether the first player wins. | Easy3 | Game theoryDynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| Stone Game 3Two players alternately take 1, 3, or 4 stones from a pile of N, and the program reports whether the first player wins with perfect play. | Easy3 | Dynamic programmingGame theory | No attempts yet | 1s | 128 MB | Judgeable |
| Stone Game 4Two players alternately take 1, 3, or 4 stones and the player taking the last stone loses; report whether the first player wins with optimal play. | Easy3 | Dynamic programmingGame theory | No attempts yet | 1s | 128 MB | Judgeable |
| Stone Game 6Two players alternately take 1, 3, or 4 stones from a pile of N, and the program prints which player wins with perfect play. | Easy3 | Game theoryDynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| Two Mysterious Alphabets from a TreeFind the max-sum root-to-leaf path in a number triangle, breaking ties by larger sum of squares, then print both sums and their mod-26 letters. | Easy3 | Dynamic programming | No attempts yet | 1s | 128 MB | Judgeable |
| Best Machine Rental ProfitEach record maps letters to profits, and the task asks for the largest sum over any contiguous block, or zero when every block loses money. | Easy3 | Dynamic programmingArray | No attempts yet | 2s | 512 MB | Judgeable |
| GeckoPick a top-row tile and move straight down, down-left, or down-right each row to maximize the mosquitoes eaten. | Easy3 | Dynamic programmingMatrix | No attempts yet | 2s | 512 MB | Judgeable |
| Grid Path CountCount right-and-down paths from the top-left to the bottom-right corner that pass through a given cell, if one is specified. | Easy3 | CombinatoricsDynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| Maximum Subarray SumFor each test case, find the maximum sum over all contiguous subarrays of the given integer array. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 256 MB | Judgeable |
| Tigger's bouncesCount length-K walks on an R by C grid where each step stays put or moves to a side neighbor, summed over all starts, modulo P per query. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 1s | 256 MB | Judgeable |
| Maximal SumFind the contiguous block of edge weights with the largest sum and print its endpoints, or print no good path when the best sum is not positive. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 64 MB | Judgeable |
| Valid Parenthesis CountCount the distinct correct parenthesis strings of length L for each test case, modulo 1000000007. | Easy3 | CombinatoricsDynamic programming+1 | No attempts yet | 2s | 256 MB | Judgeable |
| A Population of RabbitsCount rabbit pairs alive in month M given lifespan D and breeding ages up to R, starting from one newborn pair. | Easy3 | Dynamic programmingSimulation | No attempts yet | 1s | 256 MB | Judgeable |
| COWCount the subsequences equal to COW in a string of C, O, and W up to length 100000. | Easy3 | Dynamic programmingString | No attempts yet | 1s | 256 MB | Judgeable |
| Fibonacci Numbers 4Compute the nth Fibonacci number for n up to 10000 using arbitrary-precision arithmetic. | Easy3 | Dynamic programmingImplementation | No attempts yet | 1s | 256 MB | Judgeable |
| Stair Number CountCount length-N numbers with no leading zero where adjacent digits differ by 1, modulo 1,000,000,000. | Easy3 | Dynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| MovingJungyu collects the most candy possible walking from the top-left room to the bottom-right room with right, down, and diagonal moves. | Easy3 | Dynamic programmingMatrix | No attempts yet | 1s | 256 MB | Judgeable |
| Binomial Coefficient 2Compute the binomial coefficient C(N, K) modulo 10007 for N up to 1000. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 1s | 256 MB | Judgeable |
| Buying cardsGiven pack prices P_1 to P_N, choose packs whose card counts sum to exactly N to maximize the total price. | Easy3 | Dynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| Largest Sum Increasing SubsequencePick elements in order so each is larger than the last and their sum is as large as possible. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 256 MB | Judgeable |
| Ascending NumbersCount length-N digit strings, leading zeros allowed, whose digits never decrease left to right, modulo 10007. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 1s | 256 MB | Judgeable |
| LOLFind the fewest insertions, replacements, and deletions that make each given word contain lol as a contiguous substring. | Easy3 | Dynamic programmingString | No attempts yet | 1s | 256 MB | Judgeable |
| Neurotic NetworkEvaluate the weighted sum from the leaves to the root of a tree and print FREAK OUT for an even result, else the value modulo 1,000,000,007. | Easy3 | TreeDynamic programming+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Hunger GamesChoose weapons within the sack weight limit to maximize total preference. | Easy3 | Dynamic programming | No attempts yet | 3s | 256 MB | Judgeable |
| PIN Code PossibilitiesCount n-digit codes with leading zeros allowed whose digits add up to s for each test case. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 3s | 256 MB | Judgeable |
| Safe ZoneCount the K-step walks on segments 0 to N-1 with forced turns at the ends that finish inside segments P to Q. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 1s | 256 MB | Judgeable |
| Path FindingDecide for every ordered pair of vertices in a directed graph with up to 100 vertices whether a path of at least one edge connects them. | Easy3 | GraphDynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| Compositions Missing a SequenceCount the ordered compositions of n that use no part from the arithmetic progression starting at m with step k. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 1s | 256 MB | Judgeable |
| Longest Decreasing SubsequenceFind the length of the longest strictly decreasing subsequence of the given sequence. | Easy3 | Dynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| 2 by n TilingCount the ways to tile a 2 by n rectangle with 1 by 2 dominoes and print the count modulo 10007. | Easy3 | Dynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| 2 by n Tiling 2Count the ways to tile a 2 by n rectangle with dominoes and 2 by 2 squares, modulo 10007. | Easy3 | Dynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| Squawk VirusStarting from user s, propagate squawk counts along links for t minutes and report how many squawks are sent at time t. | Easy3 | Dynamic programmingGraph | No attempts yet | 1s | 256 MB | Judgeable |
| Array EscapeFind the cheapest right-and-down path through a square grid where stepping to a higher or equal neighbor costs the raises needed to exceed it. | Easy3 | Dynamic programmingShortest path+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Polynesiaglot (Small 1)Count length-L words over C consonants and V vowels in which each consonant is directly followed by a vowel, modulo 1000000007. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 5s | 512 MB | Judgeable |
| PolynesiaglotCount length-L strings over C consonants and V vowels with no adjacent consonants and no trailing consonant, modulo 1e9+7. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 5s | 512 MB | Judgeable |
| Polynesiaglot (Large)Count length-L words over C consonants and V vowels where every consonant is followed by a vowel, modulo 1e9+7. | Easy3 | Dynamic programmingCombinatorics | No attempts yet | 5s | 512 MB | Judgeable |
| Sums of 1, 2, 3 (2)Find the k-th composition of n using parts 1, 2 and 3 in lexicographic order, or print -1 when it does not exist. | Easy3 | BacktrackingDynamic programming | No attempts yet | 1s | 512 MB | Judgeable |
| Ordinary KnapsackGiven N items with weights and values, pick a subset with total weight at most K to maximize total value. | Easy3 | Dynamic programming | No attempts yet | 2s | 512 MB | Judgeable |
| Recurrence sequenceCompute the n-th term of a self-convolution recurrence where t(n) sums t(i)*t(n-1-i) for i from 0 to n-1, with n up to 35. | Easy3 | Dynamic programmingMath+2 | No attempts yet | 5s | 512 MB | Judgeable |
| Splitting the Pizza Tower (Small)A tower of N pizzas is repeatedly split into two smaller towers, each split scoring the product of the two new heights. Find the maximum total score (N ≤ 10). | Easy3 | Dynamic programmingMath+1 | No attempts yet | 1s | 512 MB | Judgeable |
| What's Your Tier?Starting at 2000 points, play 20 games with given win, loss, and draw probabilities; compute the probability of ending in each of five tiers. | Easy3 | ProbabilityDynamic programming+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Assigning roomsGiven three distinct room capacities and a student count, decide whether some nonnegative combination of the capacities sums exactly to the count. | Easy3 | Dynamic programmingMath+2 | No attempts yet | 2s | 512 MB | Judgeable |
| CrammingGiven N chapters, each with a study time and a score, choose a subset whose total study time fits in T to maximize the total score. | Easy3 | Dynamic programmingArray+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Falling ApartGiven up to 15 positive integers, two players alternately take one piece; find the final sums under optimal play. | Easy3 | Dynamic programmingGame theory+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Going Down 2Given N rows of three digits, move down choosing reachable cells and report the maximum and minimum possible sum of the digits passed through. | Easy3 | Dynamic programmingArray | No attempts yet | 1s | 512 MB | Judgeable |
| Virus OutbreakRead hour values until -1 and print the Fibonacci number a(X) for each in the format 'Hour X: Y cow(s) affected'. | Easy3 | MathDynamic programming+2 | No attempts yet | 2s | 512 MB | Judgeable |
| PotionGiven market prices and mixture recipes, compute the cheapest cost to produce one unit of the potion named LOVE. | Medium4 | GraphDynamic programming+2 | No attempts yet | 2s | 128 MB | Judgeable |
| ZooCount the ways to place non-attacking lions in a 2 by N grid so that no two lions sit in adjacent cells, modulo 9901. | Medium4 | Dynamic programmingCombinatorics+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Infinite SequenceCompute the N-th term of a sequence where A_i equals A at floor(i/P) plus A at floor(i/Q), using memoized recursion for huge N. | Medium4 | RecursionDynamic programming+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Tournament WinnerGiven all pairwise win probabilities among 8 players in a fixed single-elimination bracket, compute each player's probability of winning the whole tournament. | Medium4 | ProbabilityDynamic programming+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Highway ShortcutsCompute the minimum driving distance from position 0 to D on a highway with up to 12 one-way shortcuts that skip forward sections. | Medium4 | Shortest pathGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |