Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

Total results3,128 problems

		Topics				Judge
Letter BoardCount the number of paths on an N by M letter grid that spell a given word, moving 1 to K cells in one straight direction per step.	Medium5	Dynamic programmingMatrix+1	No attempts yet	2s	128 MB	Judgeable
String CopyFind the minimum number of substring-copy operations from S needed to reconstruct P using greedy/DP over matching positions.	Medium5	Dynamic programmingString+1	No attempts yet	2s	128 MB	Judgeable
Marbles in BoxesGiven two marble sequences and a pairwise score table, choose a sequence of pop/pop/pop-both operations to maximize total matched-pair score, using LCS-like DP with reconstruction.	Medium5	Dynamic programmingArray+1	No attempts yet	2s	128 MB	Judgeable
Team FormationPartition an age-ordered score sequence into contiguous groups to maximize the sum of each group's max-minus-min score.	Medium5	Dynamic programmingArray+1	No attempts yet	2s	128 MB	Judgeable
Sequence ReductionDecide if repeatedly merging adjacent elements as A[i]-A[i+1] can reduce the sequence to a single target value T.	Medium5	Dynamic programmingRecursion	No attempts yet	2s	128 MB	Judgeable
Plum TreeGiven a sequence of falling trees over T seconds, find the max plums caught starting at tree 1 with at most W moves between trees.	Medium5	Dynamic programming	No attempts yet	2s	128 MB	Judgeable
JumpFind the minimum number of jumps from stone 1 to stone N where jump lengths change by at most 1 each step and some stones are blocked.	Medium5	Dynamic programmingBFS+1	No attempts yet	2s	128 MB	Judgeable
Theater SeatsCount permutations where each ticket holder sits in their own or adjacent seat, with VIP seats fixed and splitting the row into independent segments counted by a Fibonacci-like recurrence.	Medium5	Dynamic programmingCombinatorics+1	No attempts yet	2s	128 MB	Judgeable
Buying JewelsFor each of n rows pick a contiguous non-empty subarray maximizing summed total value, breaking ties by fewest jewels then lexicographically smallest index sequence.	Medium5	Dynamic programmingArray+1	No attempts yet	2s	128 MB	Judgeable
Tree CuttingGiven a tree with n vertices, find the minimum number of edges to cut so some resulting piece has exactly m vertices, or report impossibility.	Medium5	TreeDynamic programming+1	No attempts yet	2s	128 MB	Judgeable
Fax CompressionChoose a quantization of a sequence into 4 levels with run-length style bit encoding to minimize error plus weighted code length.	Medium5	Dynamic programmingString+1	No attempts yet	2s	128 MB	Judgeable
Dance Pad Minimum EnergyGiven a sequence of dance pad moves, compute the minimum total energy to press each in order by choosing which of two feet to move each time.	Medium5	Dynamic programmingSimulation	No attempts yet	2s	128 MB	Judgeable
Polygon PartitionsCount noncrossing dissections of a regular N-gon into all triangles or all quadrilaterals, modulo 1e9, using Catalan-like combinatorics.	Medium5	CombinatoricsDynamic programming+1	No attempts yet	2s	128 MB	Judgeable
Number of PermutationsGiven a permutation's up-down pattern, count permutations of size n sharing the same pattern, modulo 1,000,000,000.	Medium5	Dynamic programmingCombinatorics	No attempts yet	2s	128 MB	Judgeable
Sum of Powers of TwoCount the ways to write N as an unordered sum of powers of two, modulo one billion.	Medium5	Dynamic programmingMath+1	No attempts yet	2s	128 MB	Judgeable
Brotherly Field DivisionChoose a non-decreasing staircase cut across N columns of an N x N grid to minimize the harvest difference between the two regions, and output one such cut.	Medium5	Dynamic programmingBrute force+1	No attempts yet	1s	256 MB	Judgeable
ParameciaSimulate a population where each individual matures, reproduces daily within an age window, dies at a fixed age, and count survivors on day N modulo 1000.	Medium5	Dynamic programmingSimulation+1	No attempts yet	1s	128 MB	Judgeable
Electric WiresGiven wires connecting positions on two poles, find the minimum removals so remaining wires never cross, equivalent to n minus the longest increasing subsequence.	Medium5	Dynamic programmingBinary search+1	No attempts yet	1s	128 MB	Judgeable
Crossing the Stone BridgesCount ways to match a scroll string to positions across two parallel bridge strings, alternating bridges and strictly increasing positions.	Medium5	Dynamic programmingString	No attempts yet	1s	128 MB	Judgeable
Corporate InvestmentAllocate exactly N integer units of money across M companies using given profit tables to maximize total profit, then output an allocation, a classic knapsack-style DP task.	Medium5	Dynamic programmingArray+1	No attempts yet	1s	128 MB	Judgeable
Submarine IdentificationDecide whether a binary string can be split into pieces of '01' or '1' followed by at least two 0s and at least one 1, using pattern matching or DP.	Medium5	Dynamic programmingString matching+1	No attempts yet	1s	128 MB	Judgeable
Glass BallsGiven B balls and M floors, compute the minimum number of drops needed to guarantee finding the critical breaking floor in the worst case.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	128 MB	Judgeable
Adjacent Bit Pair CountCount binary strings of length n whose number of adjacent 11-pairs equals a given k, for up to 1000 queries.	Medium5	Dynamic programmingCombinatorics+1	No attempts yet	1s	128 MB	Judgeable
KnightSimulate a knight's moves on an N x N board for T steps (T up to a million), where each square can only be entered at time-multiples of its written value, and output all possible final squares.	Medium5	BFSSimulation+1	No attempts yet	1s	128 MB	Judgeable
Dongjun's GameGiven N level scores, find the minimum total decrease needed to make the sequence strictly increasing while all scores stay positive.	Medium5	GreedyArray+1	No attempts yet	1s	128 MB	Judgeable
Pleasant WordCount ways to fill blanks in a word with uppercase letters so it avoids three consecutive vowels or consonants and contains at least one 'L'.	Medium5	Dynamic programmingString+1	No attempts yet	1s	128 MB	Judgeable
DebugGiven a binary R by C grid, find the largest square submatrix (side at least 2) that is invariant under 180-degree rotation, or output -1.	Medium5	Dynamic programmingMatrix+1	No attempts yet	5s	128 MB	Judgeable
FootnotesGiven text lines and footnotes attached to specific lines, compute the minimum number of pages so that each page holds consecutive text lines plus their footnotes within a line limit K.	Medium5	Dynamic programmingGreedy+1	No attempts yet	1s	128 MB	Judgeable
Foot TypingGiven two words and their interleaving, output the lexicographically smallest sequence of 1s and 2s marking which word produced each character.	Medium5	Dynamic programmingString+1	No attempts yet	1s	128 MB	Judgeable
ExchangeGiven daily buy and sell exchange rates between marks and dollars, compute the maximum marks obtainable after N days starting from 100 marks, output as a reduced fraction.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	128 MB	Judgeable
Friends Calling PlanGiven call minutes between up to 16 employees, pair them all up to minimize total billing cost using bitmask DP over perfect matchings.	Medium5	Dynamic programmingBit manipulation+1	No attempts yet	1s	128 MB	Judgeable
Hop, HopCount, modulo 1000000, the number of ways to write n as a non-increasing sequence of jumps of length 1, 2, or 3, for n up to 1e9.	Medium5	MathDynamic programming+1	No attempts yet	1s	128 MB	Judgeable
Ancient ManuscriptCount ways to fill '*' letters in a word so runs of vowels/consonants respect maximum length and maximum equal-letter-repeat limits, using DP over letter classes and previous letter identity.	Medium5	Dynamic programmingString+1	No attempts yet	1s	128 MB	Judgeable
Decoding Morse SequencesCount the number of ways to split a given Morse code string into a sequence of dictionary words, using dynamic programming with Morse-to-word conversion.	Medium5	Dynamic programmingString+1	No attempts yet	1s	128 MB	Judgeable
Sangkeun TowerFor each elevator, find the minimum floor above 0 reachable using exactly n button presses (up/down moves), never going below 0, then take the overall minimum across elevators.	Medium5	Dynamic programmingBrute force+1	No attempts yet	1s	128 MB	Judgeable
Graph MatchingCount the number of matchings (independent edge sets) of the cycle graph C_n for each given n, likely requiring big-integer arithmetic via a Lucas-sequence style recurrence.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	128 MB	Judgeable
ComputersGiven a fixed replacement cost and arbitrary maintenance costs for owning a computer over any year range, find the minimum total cost to cover n years using dynamic programming.	Medium5	Dynamic programmingArray	No attempts yet	1s	128 MB	Judgeable
Game, Set and MatchGiven the per-point win probability p, compute the probabilities of winning a tennis game, set, and match using the standard scoring rules.	Medium5	Dynamic programmingProbability+2	No attempts yet	1s	128 MB	Judgeable
Minimal BackgammonSimulate turn by turn probability mass over board positions (with lose-a-turn and go-to-start squares, and bounce-back overshoot rule) to find probability of reaching the goal within T turns.	Medium5	Dynamic programmingSimulation+1	No attempts yet	1s	128 MB	Judgeable
Sum of Distinct PrimesCount subsets of k distinct primes summing to n, using dynamic programming over sieve-generated primes up to 1120.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	128 MB	Judgeable
Maximum SumGiven n boxes of numbered balls, pick at most one ball per box in order to form a non-decreasing sequence with maximum possible sum.	Medium5	Dynamic programmingSorting	No attempts yet	1s	128 MB	Judgeable
Faulhaber's TriangleBuild Faulhaber's triangle row by row using the recurrence F(i,j)=i/j*F(i-1,j-1) plus the normalization that each row sums to 1, then answer queries for F(m,k) as reduced fractions.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	128 MB	Judgeable
CounterattackTwo strikers advance in lockstep through n points, each step either dribbling or passing to the partner; find the cheapest route from a long pass at point 1 to a shot at point n.	Medium5	Dynamic programmingArray+1	No attempts yet	1s	256 MB	Judgeable
Pro-Test VotingGiven a budget and precincts whose vote gain follows a concave spending curve, allocate dollars to maximize rounded total votes, breaking ties toward lower-numbered precincts.	Medium5	Dynamic programmingGreedy	No attempts yet	1s	128 MB	Judgeable
Largest SquareGiven a 0/1 matrix, find the side length of the largest all-ones square submatrix.	Medium5	Dynamic programmingMatrix	No attempts yet	5s	256 MB	Judgeable
SkylineCount permutations of 1..N with no increasing subsequence of length 3, modulo 1,000,000, for each N up to 1,000.	Medium5	Dynamic programmingCombinatorics+1	No attempts yet	1s	128 MB	Judgeable
Ferry Loading VGiven distinct vehicle weights, split them between two lanes so the totals differ as little as possible. Output the minimum difference.	Medium5	Dynamic programmingPrefix sum+1	No attempts yet	1s	128 MB	Judgeable
Scrolling SignGiven k-wide words, find the minimum total letters scrolled in so that each word appears in order, allowing overlap between consecutive words.	Medium5	Dynamic programmingString+2	No attempts yet	1s	128 MB	Judgeable
Catamaran BallastSplit the given rock weights between two hulls so the difference of the two sums is as small as possible.	Medium5	Dynamic programmingBrute force	No attempts yet	1s	128 MB	Judgeable
Multiplication GameAlice and Bob multiply a running product by 2 to 9 in turn; find who forces the product to reach n first with optimal play.	Medium5	Game theoryDynamic programming+1	No attempts yet	1s	128 MB	Judgeable
Tight WordsCount words of length n over digits 0..k where adjacent digits differ by at most 1, then print that count as a percentage rounded to five decimals.	Medium5	Dynamic programmingCombinatorics+2	No attempts yet	1s	128 MB	Judgeable
Splitting Teams FairlySplit N people into two teams differing in size by at most one so their total weight difference is minimized, then print both totals in increasing order.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Old Wine Into New BottlesGiven a wine volume and bottle sizes with min and max capacities, maximize the bottled amount and print the leftover in millilitres.	Medium5	Dynamic programmingGreedy+1	No attempts yet	1s	128 MB	Judgeable
Ferry LoadingLoad the longest prefix of cars onto two lanes of bounded total length, choosing lanes to maximize cars loaded and break ties lexicographically.	Medium5	Dynamic programmingGreedy	No attempts yet	1s	128 MB	Judgeable
Hippity HopscotchOn an n by n grid of penny stacks, starting at (0,0) and jumping up to k cells in a row or column to a strictly larger stack, find the maximum total collected.	Medium5	Dynamic programmingSorting+1	No attempts yet	1s	128 MB	Judgeable
PlinkoGiven rigged Plinko boards with per-peg right-move probabilities, compute for each start and end column the number of distinct paths and the truncated percentage chance.	Medium5	Dynamic programmingProbability+2	No attempts yet	1s	128 MB	Judgeable
RIPOFFA token moves 1 to S squares per turn and must exit a board of N labeled squares within T turns; maximize the total of the squares landed on.	Medium5	Dynamic programmingSliding window	No attempts yet	1s	128 MB	Judgeable
Signal StrengthFind the maximum signal strength reaching switch N-1 from switch 0 through a switch network with gain or loss multipliers on nodes and edges.	Medium5	GraphDFS+2	No attempts yet	1s	128 MB	Judgeable
RailroadGiven two sequences, decide whether a target sequence can be formed by repeatedly taking the front car of either train; once one train empties, the rest follow in order.	Medium5	Dynamic programmingTwo pointers+2	No attempts yet	1s	128 MB	Judgeable
PERMSFor each query (n, k), count permutations of 1..n having exactly k inversions, with n up to 18 and k up to 200.	Medium5	Dynamic programmingCombinatorics+2	No attempts yet	1s	128 MB	Judgeable
Sequence WalkingGiven two ascending integer sequences, find the maximum sum of a forward walk that may switch sequences at shared values.	Medium5	Dynamic programmingTwo pointers	No attempts yet	1s	128 MB	Judgeable
Robots on a GridCount monotone right/down paths from the top-left to the bottom-right of an n by n grid with blocked cells, modulo 2^31-1, and report whether the goal is reachable at all, or reachable only with up and left moves allowed.	Medium5	Dynamic programmingDFS+2	No attempts yet	1s	128 MB	Judgeable
lsGiven a wildcard pattern where * matches any run of characters, print the input file names that match it, keeping input order.	Medium5	Dynamic programmingString+2	No attempts yet	1s	128 MB	Judgeable
Rig PlacementGiven n oil fields, a per-field investment cap m, and a total budget B, pick an investment amount for each field so total oil is maximized.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Study DaysDistribute H study hours among n courses, each with 10 grade thresholds, to maximize the average grade point, rounded to two decimals.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Yes or No?Pick between l and r questions to answer Yes, maximizing the sum of per-question expected correct probabilities, and report the maximum expectation to two decimals.	Medium5	Dynamic programmingSorting+2	No attempts yet	1s	128 MB	Judgeable
Biomedical EngineeringGiven a target string and a set of reusable component strings, find the minimum number of components whose concatenation equals the target, or report that it is impossible.	Medium5	Dynamic programmingString+2	No attempts yet	1s	128 MB	Judgeable
GerrymanderingSplit n precincts, each with P and Q vote counts, into two nonempty districts; find how many districts P can win (0, 1, or 2).	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
SoccerCompute probability distribution of final scores after up to T seconds of a stochastic soccer simulation with passing, stealing, shooting, and absorbing states.	Medium5	ProbabilityDynamic programming+2	No attempts yet	2s	128 MB	Judgeable
Battleground PreservationGiven past battle results with costs, find the cheapest chain of victories between two fighters and decide the winner, or output FIGHT! if neither dominates.	Medium5	GraphShortest path+2	No attempts yet	1s	128 MB	Judgeable
Life ConnectionsGiven an undirected friendship graph, count the distinct shortest paths between each queried pair of nodes, where path length counts nodes.	Medium5	GraphBFS+2	No attempts yet	1s	128 MB	Judgeable
MessageGiven error and succession probabilities for a Martian alphabet, find the most likely original word for each intercepted message using maximum likelihood.	Medium5	Dynamic programmingProbability	No attempts yet	1s	128 MB	Judgeable
Stock MarketFind the contiguous subarray with the largest sum and report its 1-based start and end indices, breaking ties by smallest start then smallest end.	Medium5	Dynamic programmingGreedy	No attempts yet	1s	256 MB	Judgeable
Venus RoverChoose which stones to collect so total value is maximized, given limits on time and total lifted mass.	Medium5	Dynamic programming	No attempts yet	1s	128 MB	Judgeable
FashionistaFor each day pick any clothing whose temperature range covers that day's high, maximizing the sum of absolute flashiness differences between consecutive days.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
JOI FlagCount fillings of an M by N grid with J, O, I (some cells fixed) that contain at least one L shape: J with O to its right and I below, modulo 100000.	Medium5	Dynamic programmingCombinatorics+2	No attempts yet	5s	128 MB	Judgeable
Commute RouteCount monotone lattice paths from (1,1) to (w,h) that never turn at two consecutive intersections, modulo 100000.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
StrollSimulate the letters on a grid as N successive walks from the top-left, and report the endpoint of the N-th walk.	Medium5	SimulationDynamic programming+1	No attempts yet	2s	128 MB	Judgeable
Longest Common SubstringGiven two uppercase strings of length up to 4000, find the length of the longest substring that occurs contiguously in both.	Medium5	Dynamic programmingString+2	No attempts yet	2s	256 MB	Judgeable
FloodgatesEach gate drains Fi per hour at fixed cost Ci when opened. For each query (V, T), find the minimum total cost whose combined capacity Fi*T covers V.	Medium5	Brute forceGreedy+2	No attempts yet	1s	128 MB	Judgeable
Child PlayGiven domino-like slabs, orient and order them so both rows sum equally, discarding one slab only if necessary and preferring the smallest minimum half.	Medium5	Dynamic programmingGreedy+2	No attempts yet	1s	128 MB	Judgeable
SupermarketGiven a shopping list and products in path order, buy the list items in order from later positions at minimum total cost, or report impossible.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Milk SchedulingGiven task durations and precedence constraints that form a DAG, find the minimum makespan when unlimited workers milk cows in parallel.	Medium5	GraphTopological sort+2	No attempts yet	1s	128 MB	Judgeable
BookshelfPartition the books in order into shelves whose widths sum to at most L, minimizing the total of each shelf's maximum height.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Hay For SaleGiven a wagon capacity and a list of hay bale volumes, find the largest total volume not exceeding the capacity that can be formed by choosing whole bales.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Cow Digit GameFor each starting number, players alternately subtract its largest or smallest nonzero digit, and the player who reaches 0 wins; decide if the first player wins.	Medium5	Dynamic programmingGame theory+2	No attempts yet	1s	128 MB	Judgeable
Cow CashCount the number of unordered ways to make an amount N using V coin denominations, where each coin can be used any number of times.	Medium5	Dynamic programmingCombinatorics+1	No attempts yet	1s	128 MB	Judgeable
Charm BraceletChoose a subset of N charms, each with a weight and a desirability, so that total weight stays within M and total desirability is maximized.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Cow ContestGiven the winners of head-to-head matches, count how many cows have a skill rank that is fully forced by the results.	Medium5	GraphDFS+2	No attempts yet	1s	128 MB	Judgeable
Cow TravellingCount the number of walks of exactly T steps on a grid from a start cell to a target cell, where each step moves to a vertically or horizontally adjacent open cell.	Medium5	Dynamic programmingMatrix+2	No attempts yet	1s	128 MB	Judgeable
ATM PIN TheftGiven a sequence of observed key presses (digits and at most one backspace), count the four-digit PINs that could produce exactly that sequence of pressed keys.	Medium5	Dynamic programmingCombinatorics+2	No attempts yet	1s	128 MB	Judgeable
Hopeless CoachGiven past win, draw, and loss counts, find the probability that the team earns at least P points over the next N matches.	Medium5	Dynamic programmingProbability+2	No attempts yet	1s	128 MB	Judgeable
String ComputerCompute the minimum number of single-character insert, delete, or change operations needed to turn one string into another.	Medium5	Dynamic programmingString+2	No attempts yet	1s	128 MB	Judgeable
Extrapolation Using a Difference TableExtend a sequence by k steps using a polynomial difference table, always assuming the highest-order differences stay constant, and print the (n+k)-th term.	Medium5	MathDynamic programming+2	No attempts yet	1s	128 MB	Judgeable
El DoradoCount the increasing subsequences of length exactly k in a sequence of n distinct numbers, for several test cases.	Medium5	Dynamic programmingArray+1	No attempts yet	1s	128 MB	Judgeable
A Game with MarblesEach move takes one marble from a bowl and, if it is not bowl 1, adds one marble to every lower-numbered bowl; count the total moves until all bowls are empty.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	128 MB	Judgeable
France '98Given win probabilities for every pair of 16 teams and a fixed bracket, compute each team's probability of winning the single-elimination tournament.	Medium5	Dynamic programmingProbability+2	No attempts yet	1s	128 MB	Judgeable
Humble NumbersFor each n up to 5842, print the nth number whose only prime factors are 2, 3, 5, or 7, formatted with the correct English ordinal suffix.	Medium5	Dynamic programmingMath+2	No attempts yet	1s	128 MB	Judgeable
Spiderman's WorkoutAssign plus or minus signs to the distances so the partial sums stay at or above 0 and return to 0 at the end, minimizing the peak height.	Medium5	Dynamic programmingGreedy+2	No attempts yet	1s	128 MB	Judgeable
Median Weight BeadGiven weighted comparisons between beads, count how many beads cannot be the median because at least (N+1)/2 beads are known heavier or lighter.	Medium5	GraphDFS+2	No attempts yet	1s	128 MB	Judgeable