Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

Total results3,128 problems

		Topics				Judge
Fruit FeastEat unlimited fruits that add A or B without passing T, using at most one halving, to reach the largest fullness.	Medium5	Dynamic programming	No attempts yet	2s	512 MB	Judgeable
Radio ContactJohn and Bessie each walk or wait along their fixed routes to minimize the summed squared distance until both reach their final points.	Medium5	Dynamic programming	No attempts yet	2s	512 MB	Judgeable
Circular Barn (Silver)Cows waiting at ring doors walk clockwise to fill each room with one cow at the smallest total squared walking distance.	Medium5	Dynamic programmingBrute force	No attempts yet	2s	512 MB	Judgeable
Cleaning the Club Room!Pick exactly M evenings to reset dirt to zero so the sum of daily visitors times dirt since the last cleaning is smallest.	Medium5	Dynamic programmingPrefix sum	No attempts yet	1s	128 MB	Judgeable
Not So RandomFeed X through N stages that each apply bitwise AND, OR, or XOR with K at given probabilities and report the expected final value.	Medium5	ProbabilityBit manipulation+1	No attempts yet	5s	512 MB	Judgeable
Cube IV (Large)Find the longest run of consecutive room numbers placed in neighboring cells and report its starting number and length.	Medium5	Dynamic programmingGraph+1	No attempts yet	5s	512 MB	Judgeable
Broken Calculator (Small)Split X into factors typed with working digits only, minimizing the total of digit, multiply, and equals presses.	Medium5	Dynamic programmingRecursion+1	No attempts yet	5s	512 MB	Judgeable
Parentheses Order (Small)Print the k-th valid parentheses string of n pairs in lexicographic order for each test case, or report that it does not exist.	Medium5	Dynamic programmingCombinatorics	No attempts yet	5s	512 MB	Judgeable
Parentheses Order (Large)Given n and k, output the k-th valid parentheses string of n pairs in lexicographic order, or Doesn't Exist! when fewer than k exist.	Medium5	Dynamic programmingCombinatorics+1	No attempts yet	5s	512 MB	Judgeable
Full Binary TreeGiven a tree with up to 15 nodes, delete as few nodes as possible so the remaining nodes form a full binary tree for some choice of root.	Medium5	TreeDynamic programming+1	No attempts yet	5s	512 MB	Judgeable
Dragon Maze (Small)Find the fewest-step walk from the entrance to the exit of a cell grid and report the most power gathered on such a route.	Medium5	BFSShortest path+1	No attempts yet	5s	512 MB	Judgeable
Dragon Maze (Large)In a grid with blocked cells, walk from the entrance to the exit in the fewest moves and collect the most power among such walks.	Medium5	BFSDynamic programming	No attempts yet	5s	512 MB	Judgeable
Diamond Inheritance (Large)Decide whether any pair of classes in each inheritance DAG has two different inheritance paths between them.	Medium5	GraphTopological sort+1	No attempts yet	5s	512 MB	Judgeable
Survivor (Small)Pick which foods to eat and in what order, respecting each shelf life, to maximize total survival time.	Medium5	BacktrackingDynamic programming	No attempts yet	5s	512 MB	Judgeable
Bit Count (Small)Given N, split it into nonnegative a and b with a plus b equal to N to maximize the total count of 1 bits in a and b.	Medium5	Bit manipulationDynamic programming	No attempts yet	5s	512 MB	Judgeable
Doubly-sorted grid (small)Given a partially filled R by C letter grid with R and C at most 4, count the completions whose rows and columns are non-decreasing modulo 10007.	Medium5	BacktrackingDynamic programming	No attempts yet	5s	512 MB	Judgeable
Counting welcome to code jam subsequencesCount subsequences of each input text that spell the 19-character target string, printed as the last four digits.	Medium5	Dynamic programmingString	No attempts yet	5s	512 MB	Judgeable
Cheating a Boolean Tree (Small)Given a complete boolean tree with switchable gates, find the minimum number of gate flips so the root evaluates to V.	Medium5	TreeDynamic programming	No attempts yet	5s	512 MB	Judgeable
Cheating a Boolean Tree (Large)Given a complete binary tree of AND/OR gates with fixed leaf values, find the fewest changeable gates to flip so the root equals V, or report IMPOSSIBLE.	Medium5	Dynamic programmingTree+2	No attempts yet	5s	512 MB	Judgeable
Longest Increasing Subsequence 3Given a sequence of up to 10^6 integers, find the length of the longest strictly increasing subsequence.	Medium5	Dynamic programmingBinary search	No attempts yet	3s	512 MB	Judgeable
Roller CoasterFrom a sequence of column heights, delete columns so the survivors strictly decrease then strictly increase (either part may be empty); output the maximum number of survivors.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
String TheoryGiven alternating runs of quote characters, find the largest k for which the whole string is a k-quotation.	Medium5	Dynamic programmingString+1	No attempts yet	2s	512 MB	Judgeable
Inha SuitStarting at height 1, choose one of five moves before each tree so the height lands on a hole, minimizing teleport (T) uses within limit K.	Medium5	Dynamic programmingGraph+1	No attempts yet	1s	128 MB	Judgeable
A Walk Around the Main CampusCount closed walks of exactly D minutes from the Information Science Building in a fixed eight-building graph, modulo 1e9+7.	Medium5	Dynamic programmingGraph+1	No attempts yet	1s	512 MB	Judgeable
Make It One 2Find the fewest operations (divide by 3, divide by 2, or subtract 1) turning N into 1, and print the lexicographically smallest shortest path.	Medium5	Dynamic programmingBFS+1	No attempts yet	0.5s	512 MB	Judgeable
Junseo the Librarian KingGiven book numbers and weights, move the lightest total weight of books so the numbers end up in non-decreasing order.	Medium5	Dynamic programmingSorting+2	No attempts yet	2s	512 MB	Judgeable
Cheating a Boolean TreeIn a tournament-style Boolean tree, flip the fewest changeable AND/OR gates so the root evaluates to V, or report it impossible.	Medium5	TreeDynamic programming	No attempts yet	2s	512 MB	Judgeable
Handing out candiesFor every K, count the ways to choose one candy of each brand 1 through K, and print the total over all K.	Medium5	Dynamic programmingCombinatorics	No attempts yet	2s	512 MB	Judgeable
Magic PotionGiven a complete graph with edge weights and K potions that halve one trip's time, find the shortest time from city 0 to city 1.	Medium5	Shortest pathGraph+1	No attempts yet	2s	512 MB	Judgeable
Counting Music ScoresCount scores over two pitches and two durations with n seconds total, balanced pitch counts, at least as many long notes as short, and alternating pitches starting low.	Medium5	CombinatoricsDynamic programming+1	No attempts yet	2s	512 MB	Judgeable
Selling CPUsSell up to c CPUs across m ordered merchants, each paying p_i for exactly i CPUs in one deal, to maximize total money.	Medium5	Dynamic programmingGreedy	No attempts yet	2s	512 MB	Judgeable
MazeBob moves through a multi-graph where each letter opens doors with that label; given the letter sequence, compute the probability he reaches room n, choosing uniformly among available matching doors.	Medium5	ProbabilityDynamic programming+2	No attempts yet	2s	512 MB	Judgeable
Spontaneous TripGiven flight counts between airports, find the most likely airport reached after exactly K random flights starting from ICN.	Medium5	ProbabilityDynamic programming+1	No attempts yet	3s	256 MB	Judgeable
Train Line ConstructionOn an N by N grid with resident counts and blocked cells, find a 4-direction path between two stations minimizing the sum of cell weights along it.	Medium5	GraphShortest path+2	No attempts yet	1s	64 MB	Judgeable
Lucky TicketsCount digit strings of length 2N whose first N digits sum to the same value as the last N digits, modulo 1e9+7.	Medium5	Dynamic programmingCombinatorics+2	No attempts yet	2s	512 MB	Judgeable
EcologyCompute the probability that exactly M of N birds wear a tracker after D days of catching C random birds each day.	Medium5	Dynamic programmingProbability+1	No attempts yet	2s	512 MB	Judgeable
Fibonacci ChickenGiven N, split it into Fibonacci-derived (people, chicken) pairs whose people counts sum to N, and report the minimum and maximum total chickens.	Medium5	Dynamic programmingMath+2	No attempts yet	1s	128 MB	Judgeable
ResortChoose one-day, 3-day, and 5-day passes over a vacation with blocked days so every open day is covered at minimum cost, where 3 coupons buy a free one-day pass.	Medium5	Dynamic programmingGreedy+1	No attempts yet	2s	512 MB	Judgeable
Equal leaf distancesRaise edge weights in a weighted perfect binary tree so every root-to-leaf path has equal length, minimizing the total weight.	Medium5	TreeGreedy+2	No attempts yet	1s	512 MB	Judgeable
Contiguous Sum 2Find the maximum contiguous subarray sum after optionally deleting at most one element from the sequence.	Medium5	Dynamic programmingArray	No attempts yet	2s	512 MB	Judgeable
Hard CutsFor each w by h rectangle, find the minimum number of integer-sided squares that tile it exactly.	Medium5	Dynamic programmingImplementation	No attempts yet	2s	256 MB	Judgeable
Jewelry StoreWith unlimited gems of each of N kinds, list all total values obtainable by choosing exactly K gems.	Medium5	Dynamic programmingCombinatorics	No attempts yet	5s	512 MB	Judgeable
Stock exchangeGiven daily prices and a fixed fee per buy, find the maximum total profit when holding at most one share at a time and each share must be sold later.	Medium5	Dynamic programmingGreedy+2	No attempts yet	1s	512 MB	Judgeable
Sum of FactorialsGiven N up to 100000, find the fewest factorials (repeats allowed) whose sum equals N.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	512 MB	Judgeable
VampiresGiven two life totals, a hit threshold and a fixed damage, find the probability that vampire 1 wins a turn-based drain fight.	Medium5	ProbabilityDynamic programming+1	No attempts yet	2s	512 MB	Judgeable
Sentence ReductionGiven tasks with weekday, start and end times, and point values, pick a non-overlapping set that maximizes total points, and report the per-day breakdown.	Medium5	Dynamic programmingSorting+2	No attempts yet	2s	512 MB	Judgeable
Sum Decomposition 2Count ordered K-tuples of integers between 0 and N whose sum is N, modulo 1,000,000,000.	Medium5	Dynamic programmingCombinatorics+1	No attempts yet	1s	512 MB	Judgeable
Good Positions in a PermutationCount permutations of 1..N whose number of positions i with \|P_i - i\| = 1 equals a given K, modulo 1e9+7.	Medium5	CombinatoricsDynamic programming+1	No attempts yet	2s	512 MB	Judgeable
Alphabet StringInsert the fewest lowercase letters into s so that deleting some letters leaves exactly a through z in order.	Medium5	Dynamic programmingString+2	No attempts yet	2s	512 MB	Judgeable
Gather on the ClockCards sit on a ring; repeatedly stack a card onto its clockwise neighbor for the value difference, and maximize the total score when one card remains.	Medium5	Dynamic programmingIntervals	No attempts yet	8s	512 MB	Judgeable
m-ary PartitionsCount the partitions of n into powers of m, for up to 1000 queries with n up to 10000.	Medium5	Dynamic programmingMath+2	No attempts yet	2s	512 MB	Judgeable
Opening Day 2Given wok sizes, each cooking uses one or two distinct woks and produces the sum of their sizes; find the minimum number of cookings summing to exactly N.	Medium5	Dynamic programmingGreedy+2	No attempts yet	1s	256 MB	Judgeable
Grand OpeningGiven N bowls to produce and a multiset of wok sizes, each round uses one wok or two distinct woks of equal size, and you must reach exactly N bowls with the fewest rounds.	Medium5	Dynamic programmingGreedy+2	No attempts yet	1s	256 MB	Judgeable
Banknotes and RouletteSplit banknotes so the two equal-sum groups leave the smallest leftover, then add half of twice that leftover to each person's total.	Medium5	Dynamic programmingArray+2	No attempts yet	2s	512 MB	Judgeable
EmoticonsStarting from one emoticon on screen with an empty clipboard, find the minimum seconds to reach exactly S using copy, paste, and delete-one operations.	Medium5	BFSGraph+2	No attempts yet	2s	512 MB	Judgeable
Score of a SubsequenceFind the maximum over all contiguous subarrays of the weighted sum where the k-th element from the subarray start contributes k times its value.	Medium5	Dynamic programmingArray+2	No attempts yet	2s	512 MB	Judgeable
Connecting Edges 2Given a weighted edge list, pick the order of adding edges that makes the total weight added up to the moment s and t first become connected as small as possible.	Medium5	GraphSorting+2	No attempts yet	2s	512 MB	Judgeable
Vote (Large)Given N supporters of A and M of B in random arrival order, find the probability A leads after every vote; a ballot-problem computation.	Medium5	CombinatoricsProbability+2	No attempts yet	5s	512 MB	Judgeable
Codejamon Cipher (Small)For each enciphered string, count the sentences of vocabulary words whose letter multisets concatenate to it, modulo 1e9+7.	Medium5	Dynamic programmingHash map+1	No attempts yet	5s	512 MB	Judgeable
Slides! (Small)Given B up to 6 and M up to 20, decide if exactly M paths from building 1 to B exist, and print the fixed-rule matrix when possible.	Medium5	CombinatoricsDynamic programming+1	No attempts yet	5s	512 MB	Judgeable
Integer SequenceGiven x, y, the last two digits of A0 and A1, and a large index n, print the last two digits of An where An = xAn-1 + yAn-2.	Medium5	MathDynamic programming+2	No attempts yet	0.25s	512 MB	Judgeable
What Is Dynamic Programming?Count paths from the top-left cell to the bottom-right cell of an n by m grid when each step moves right, down, or diagonally down-right, printed modulo 1e9+7.	Medium5	Dynamic programmingMatrix+1	No attempts yet	2s	512 MB	Judgeable
ResignationGiven each day's consultation length and payment, pick a non-overlapping set of jobs that all finish before day N+1 to maximize total payment.	Medium5	Dynamic programmingBrute force+1	No attempts yet	2s	512 MB	Judgeable
Mario PartyGiven a row of coin values and a die roll range, find the maximum total coins collected on any route that reaches past the star within T turns.	Medium5	Dynamic programming	No attempts yet	2s	512 MB	Judgeable
The Other WayCount the number of distinct shortest paths between two towns in a weighted undirected multigraph, modulo 10^9+9.	Medium5	GraphShortest path+1	No attempts yet	2s	256 MB	Judgeable
Image Quilting (Small)Given two H by W grayscale images, choose one pixel per row forming a connected seam (rows shift by at most one column) minimizing the sum of squared pixel differences, and output that minimum.	Medium5	Dynamic programmingImplementation	No attempts yet	1s	512 MB	Judgeable
Voter DepressionPick non-overlapping story intervals to multiply exposed voters' propensities and maximize the right-minus-left propensity gap.	Medium5	Dynamic programmingIntervals+1	No attempts yet	2s	512 MB	Judgeable
Pony Express (Small)Cities lie on a line with a horse in each; find the minimum time from city 1 to city N, switching horses at intermediate cities, subject to each horse's endurance limit.	Medium5	Dynamic programmingShortest path+1	No attempts yet	5s	512 MB	Judgeable
Tiling a 2 by N wallCount the ways to tile a 2 by N wall with 2x1, 1x2, and 1x1 tiles, modulo 1e9+7.	Medium5	Dynamic programmingCombinatorics	No attempts yet	2s	512 MB	Judgeable
From Seoul to GyeongsanChoose walking or cycling for each of N legs so the total time is at most K and the total donation is maximal.	Medium5	Dynamic programmingBrute force+1	No attempts yet	2s	512 MB	Judgeable
Project SchedulingGiven each task's duration and its prerequisite tasks, find the minimum total time to finish the whole project.	Medium5	Topological sortDynamic programming+2	No attempts yet	2s	512 MB	Judgeable
Building a ranchGiven an M by N grid with trees and rocks as obstacles, find the side length of the largest square subgrid that contains no obstacle.	Medium5	Dynamic programmingMatrix+2	No attempts yet	1s	512 MB	Judgeable
EnigmaGiven a digit pattern with question marks and an N, find the smallest matching number with no leading zero that is divisible by N.	Medium5	Dynamic programmingMath+2	No attempts yet	1s	1024 MB	Judgeable
Front NineGiven a clamped random walk on [0,h] with step probabilities, compute the expected area under the piecewise-linear terrain over n steps.	Medium5	ProbabilityDynamic programming+2	No attempts yet	6s	512 MB	Judgeable
TilingCount the ways to tile a 3 by W rectangle with 2 by 1 dominoes, printing the result modulo 1e9+7.	Medium5	Dynamic programmingCombinatorics+2	No attempts yet	2s	512 MB	Judgeable
Sweet, sour, bitter, saltyCut edges of a rooted binary tree so that at least X resulting components each contain at least K nodes, minimizing total cut cost.	Medium5	TreeDynamic programming+2	No attempts yet	2s	512 MB	Judgeable
Candy ChainGiven a candy string and a list of paid parts (each reversible), find the maximum total value obtainable by repeatedly removing sold parts and rejoining the remainder.	Medium5	Dynamic programmingIntervals+2	No attempts yet	7s	512 MB	Judgeable
SugorokuSquares 2 to N+1 are each marked 0 or 1; find the smallest die size j such that some sequence of rolls from 1 to j reaches or passes square N+2 without landing on any square marked 1.	Medium5	Dynamic programmingBFS+2	No attempts yet	2s	512 MB	Judgeable
Hangul LCSGiven two Hangul strings of up to 1000 characters each, compute the length of their longest common subsequence in characters.	Medium5	Dynamic programmingString+2	No attempts yet	2s	512 MB	Judgeable
Counting a^i b^j c^k subsequencesCount subsequences of a string of a, b, c that read as some positive number of a's, then b's, then c's, modulo 1e9+7.	Medium5	Dynamic programmingString+1	No attempts yet	2s	512 MB	Judgeable
Consultations before resignationGiven up to 1.5 million days, each with a job of length T_i and pay P_i, pick jobs that fit before day N+1 to maximize total pay.	Medium5	Dynamic programmingArray+2	No attempts yet	2s	512 MB	Judgeable
Probability that the knight stays on the boardA knight on an N by N board makes K random moves, each of the eight directions equally likely; find the probability it is still on the board after K moves.	Medium5	Dynamic programmingProbability+2	No attempts yet	2s	512 MB	Judgeable
Pascal's triangleBuild Pascal's triangle and sum all entries inside the equilateral sub-triangle whose top cell is row R, position C, with side length W.	Medium5	ArrayDynamic programming+2	No attempts yet	1s	512 MB	Judgeable
Signal 1Choose a subset of points with distinct x-coordinates; maximize the total Euclidean length of the polyline joining them in increasing x order.	Medium5	Dynamic programmingSorting+2	No attempts yet	1.5s	128 MB	Judgeable
Roasting Emma is a barista tooGiven a weighted tree, compute for every vertex the sum of shortest distances to all other vertices.	Medium5	TreeDFS+2	No attempts yet	1.5s	128 MB	Judgeable
QueryreuQMaintain a string under append and pop-back operations, and after each operation print the number of palindromic substrings it contains.	Medium5	StringDynamic programming+2	No attempts yet	1s	1024 MB	Judgeable
Drain PipesCount the number of ways to pick quantities of each pipe type, within the given stock, so the chosen pipes sum to exactly x.	Medium5	Dynamic programmingArray+2	No attempts yet	1s	128 MB	Judgeable
Ah-Choo!Compute the least Dynamic Time Warping distance between two equal-length integer sequences, where every point must match at least one point of the other and matches cannot cross.	Medium5	Dynamic programmingArray+1	No attempts yet	1s	512 MB	Judgeable
Pen Pineapple Apple PenGiven a string of A, P, and p, find the maximum number of disjoint subsequence occurrences of the pattern p, P, A, p in order.	Medium5	GreedyString+1	No attempts yet	1s	32 MB	Judgeable
Painting ExchangeGiven who can sell to whom at what price, find the longest chain of distinct buyers starting from artist 1 where each resale price never drops below the purchase price.	Medium6	Dynamic programmingBit manipulation+2	No attempts yet	2s	128 MB	Judgeable
Park Seongwon's ProbabilityCount permutations of up to 15 numbers whose concatenation is divisible by K, and output the probability as a reduced fraction.	Medium6	Dynamic programmingBit manipulation+2	No attempts yet	2s	128 MB	Judgeable
Power PlantsGiven restart costs between plants and which plants are already on, find the minimum total cost to reach at least P working plants, or -1.	Medium6	Dynamic programmingBit manipulation+2	No attempts yet	2s	128 MB	Judgeable
Search EngineGiven directed links between websites, compute one website's trust score by summing scores of linking sites only when no cycle would result.	Medium6	GraphDFS+2	No attempts yet	2s	128 MB	Judgeable
FencesPartition up to 16 given fence lengths into disjoint triples, keep only triples that form a valid triangle, and maximize the total area.	Medium6	Dynamic programmingBit manipulation+2	No attempts yet	2s	128 MB	Judgeable
Zigzag LineupCount permutations of N distinct heights where adjacent comparisons strictly alternate, modulo 1,000,000.	Medium6	Dynamic programmingCombinatorics+1	No attempts yet	2s	128 MB	Judgeable
Road PavingFind the minimum travel time from city 1 to city N when up to K roads can be paved to cost zero, using layered shortest-path search over (node, paves used).	Medium6	Shortest pathGraph+1	No attempts yet	2s	128 MB	Judgeable
Student ShuffleCount permutations of up to 16 students so that every pair of adjacent heights differs by more than a given value K.	Medium6	Dynamic programmingBit manipulation+2	No attempts yet	2s	128 MB	Judgeable
Hexagonal NumbersGiven N up to 1,000,000, compute the minimum number of hexagonal numbers (1, 6, 15, 28, ...) that sum to N.	Medium6	Dynamic programmingMath+2	No attempts yet	2s	128 MB	Judgeable
String DistanceGiven strings O and N, find the minimum number of substring-insertion operations to turn O into N, or output -1 if impossible.	Medium6	Dynamic programmingString+2	No attempts yet	2s	128 MB	Judgeable
Christmas TreeCount the ways to decorate an N-level tree where level k needs k ornaments split evenly among chosen colors, given limited red, green and blue ornaments.	Medium6	Dynamic programmingCombinatorics+1	No attempts yet	2s	128 MB	Judgeable