Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

Total results3,128 problems

		Topics				Judge
Longest Common SubsequenceCompute the length of the longest subsequence shared by two uppercase strings of length up to 1000.	Medium4	Dynamic programming	No attempts yet	0.1s	256 MB	Judgeable
Privacy LossPick a subset of options that maximizes total security benefit without exceeding the money budget and the privacy limit.	Medium4	Dynamic programming	No attempts yet	1s	128 MB	Judgeable
StickersPick stickers from a 2 by n grid with no two sharing an edge to maximize the total score.	Medium4	Dynamic programmingArray	No attempts yet	1s	256 MB	Judgeable
Tree ColoringCount colorings of an N-node tree with K colors so adjacent nodes differ, modulo 93563.	Medium4	Dynamic programmingTree+1	No attempts yet	1s	128 MB	Judgeable
Diamond Mining ProfitsFind the contiguous period with the largest total gain across up to 2000 test cases, breaking ties by shorter length then earlier start.	Medium4	Dynamic programmingArray+1	No attempts yet	1s	128 MB	Judgeable
Sums of Distinct Natural NumbersCount the partitions of each given N into distinct positive integers, including N itself, modulo 100999.	Medium4	Dynamic programmingCombinatorics	No attempts yet	7s	128 MB	Judgeable
Joint VentureAssign each of the M modules to company A or B so total days stay within D and both budgets hold while total cost is minimized.	Medium4	Dynamic programming	No attempts yet	1s	128 MB	Judgeable
Magic Multiplying MachineChoose any subset of the given levers, including none, to maximize the product of chosen numbers modulo M.	Medium4	Dynamic programmingMath	No attempts yet	2s	64 MB	Judgeable
WalkingWalkers start at distinct times with fixed speeds, and a later starter who arrives earlier befriends the other; find the largest group where every pair meets.	Medium4	Dynamic programmingSorting	No attempts yet	1s	128 MB	Judgeable
HousingCount the unordered splits of n into parts of at least 5 for n between 5 and 100.	Medium4	Dynamic programmingCombinatorics	No attempts yet	2s	512 MB	Judgeable
PathsFind the cheapest total cost among the directed paths from node 0 to node 1 that use the fewest links.	Medium4	BFSDynamic programming	No attempts yet	2s	512 MB	Judgeable
CoinFind the fewest coins from unlimited denominations whose values sum to V and weights sum to W.	Medium4	Dynamic programming	No attempts yet	2s	1024 MB	Judgeable
Digit SumsCount positive integers up to A whose base-B digits add up to C for each query line.	Medium4	Dynamic programmingMath	No attempts yet	1s	128 MB	Judgeable
TroyanglesCount all centered triangles of `#` cells in an N-by-N grid where row i of a height-h triangle holds 2i-1 cells.	Medium4	Dynamic programmingMatrix	No attempts yet	1s	256 MB	Judgeable
Turtle ElderPick safe start and end islands in a tree so the sum of values along the path is as large as possible, staying home when the best sum is not positive.	Medium4	TreeDynamic programming	No attempts yet	5s	256 MB	Judgeable
Plane Ticket PricingSet each week's ticket price from that week's demand estimates to maximize total revenue over the remaining seats and weeks.	Medium4	Dynamic programming	No attempts yet	2s	256 MB	Judgeable
Push-UpsGiven a push-up total equal to the sum of running scores, find the largest final score reachable with the allowed scoring plays.	Medium4	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
DiamondsFind the longest subsequence of diamonds in input order with strictly rising weight and strictly falling clarity.	Medium4	Dynamic programming	No attempts yet	5s	256 MB	Judgeable
Ambiguous EncodingsCount how many letter strings map to each digit string when A is 1 through Z at 26.	Medium4	Dynamic programmingString	No attempts yet	1s	256 MB	Judgeable
Silk RoadChoose N of M days in order for the eastward moves so the sum of distance times daily badness is smallest.	Medium4	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Cow HopscotchCount paths from the top-left cell to the bottom-right cell that move strictly down and right onto cells of the opposite color.	Medium4	Dynamic programmingMatrix	No attempts yet	1s	256 MB	Judgeable
Palindrome?Answer up to a million queries asking whether a given range of the number sequence is a palindrome.	Medium4	Dynamic programmingIntervals	No attempts yet	0.5s	256 MB	Judgeable
Dormitory ReassignmentCount the permutations of N students to rooms in which no student keeps the same room.	Medium4	CombinatoricsDynamic programming	No attempts yet	1s	128 MB	Judgeable
DrinksTwo players alternately draw balls without replacement until the first red ball appears, and you compute the chance the first player draws it.	Medium4	ProbabilityDynamic programming+1	No attempts yet	2s	256 MB	Judgeable
Study Time AllocationDistribute up to H study hours among courses with tiered grade costs to maximize the average grade points.	Medium4	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Josephus Problem 3Find the number of the last person remaining after removing every K-th of N people seated in a circle.	Medium4	MathDynamic programming	No attempts yet	1s	16 MB	Judgeable
Matrix chain multiplication orderFind the parenthesization of N given matrices that minimizes the total number of scalar multiplications.	Medium4	Dynamic programmingMatrix	No attempts yet	1s	256 MB	Judgeable
Longest Increasing SubsequenceFind the length of the longest strictly increasing subsequence of the given sequence.	Medium4	Dynamic programmingBinary search	No attempts yet	1s	256 MB	Judgeable
Shortest string containing bothFind the length of the shortest string that has both given strings as subsequences.	Medium4	Dynamic programmingString	No attempts yet	1s	256 MB	Judgeable
Jump JumpStarting from the first cell, find the fewest rightward jumps bounded by each cell value to reach the last cell, or -1 when unreachable.	Medium4	Dynamic programmingGreedy	No attempts yet	1s	256 MB	Judgeable
Card GameBoth players alternately take the left or right end card to maximize their own sum, and you compute the first player best total score.	Medium4	Dynamic programmingGame theory	No attempts yet	1s	256 MB	Judgeable
Diana and the Golden ApplesPick the apples with the greatest total weight so the extra carrying time stays strictly below her lead over Humperdonkey.	Medium4	Dynamic programming	No attempts yet	2s	256 MB	Judgeable
The Knight's Scouting MissionFind the shortest knight distance from (1,1) to (r,c) on an r by c board, count those routes modulo 1000000009, and report None when unreachable.	Medium4	BFSDynamic programming	No attempts yet	2s	256 MB	Judgeable
Candy StoreCount the subsets of candy prices whose total is at least C for each test case, modulo 65537.	Medium4	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Horn BlowingCompute the probability that the summed start-up delays of N vehicles with given discrete distributions total at most T seconds.	Medium4	Dynamic programmingProbability	No attempts yet	2s	256 MB	Judgeable
FloydFor every pair of n cities, compute the cheapest directed bus fare from up to 100,000 routes and print 0 where no route connects them.	Medium4	Shortest pathGraph+1	No attempts yet	1s	256 MB	Judgeable
Word Clouds RevisitedPlace N ordered boxes of given widths and heights into width-limited rows to minimize the sum of row heights.	Medium4	Dynamic programmingPrefix sum	No attempts yet	2s	256 MB	Judgeable
Polynomial GameFor each test case, compute the coefficient of x^N in the product of (1+x+...+x^i) for i from 1 to k.	Medium4	Dynamic programmingCombinatorics	No attempts yet	1s	256 MB	Judgeable
Mingyun's SchemeGiven N cards in order, compute the length of the longest strictly increasing subsequence.	Medium4	Dynamic programmingBinary search	No attempts yet	1s	256 MB	Judgeable
Box Splitting GameDecide whether the first or second player wins the two-box stone-splitting game from starting counts N and M.	Medium4	Game theoryDynamic programming	No attempts yet	2s	512 MB	Judgeable
Stock Purchase PlanFor each test case, decide whether the daily prices contain a strictly increasing subsequence of length K.	Medium4	Dynamic programmingBinary search	No attempts yet	5s	512 MB	Judgeable
Longest Increasing Subsequence 2Given up to 1,000,000 numbers, compute the length of the longest strictly increasing subsequence.	Medium4	Binary searchDynamic programming	No attempts yet	1s	512 MB	Judgeable
ABC StreetStarting from block 1, hop forward across A, B, C blocks in repeating order to reach block N while minimizing the sum of squared jump lengths.	Medium4	Dynamic programming	No attempts yet	2s	512 MB	Judgeable
Cube IV (Small)Given a square grid holding 1 to S squared, find the smallest start of the longest chain that steps to an orthogonal neighbor one higher and report its length.	Medium4	DFSDynamic programming+1	No attempts yet	5s	512 MB	Judgeable
Manage your Energy (Small)Allocate limited energy across ordered activities, regaining R after each up to cap E, to maximize value times energy spent.	Medium4	Dynamic programming	No attempts yet	5s	512 MB	Judgeable
Ocean ViewDestroy as few houses as possible so the heights of the houses left standing grow strictly from the lake eastward.	Medium4	Dynamic programming	No attempts yet	5s	512 MB	Judgeable
Quake Live Team SplitSplit an even number of players with given skill levels into two equal-size teams so the team totals differ as little as possible.	Medium4	Dynamic programmingBrute force	No attempts yet	5s	512 MB	Judgeable
Welcome to Code Jam (Small)Count how many ways the 19-character phrase "welcome to code jam" appears as a subsequence of the input line, and print the last four digits.	Medium4	Dynamic programmingString	No attempts yet	5s	512 MB	Judgeable
Road Network of a Perfect Binary TreeFind the minimum number of cars whose vertex-disjoint paths cover every vertex of a perfect binary tree of height H exactly once.	Medium4	TreeDynamic programming+1	No attempts yet	2s	512 MB	Judgeable
CandySum 2^K over all subsets of N candies with K elements, where the empty subset contributes 0, modulo 1,000,000,007.	Medium4	CombinatoricsMath+2	No attempts yet	2s	512 MB	Judgeable
Partitioning a QueueCount compositions of n whose parts avoid the arithmetic progression m, m+k, m+2k, with n up to 30 and up to 10000 test cases.	Medium4	Dynamic programmingCombinatorics+1	No attempts yet	2s	512 MB	Judgeable
CombinationsGiven up to 1000 pairs (n, k), compute the binomial coefficient C(n, k) modulo 10^9+7 for each pair.	Medium4	CombinatoricsMath+2	No attempts yet	2s	512 MB	Judgeable
Lab SchedulePick days to experiment so no two chosen days are within two days of each other, maximizing the sum of visit probabilities.	Medium4	Dynamic programmingGreedy	No attempts yet	2s	512 MB	Judgeable
HamletGiven a DAG of plot states where each action gives a probability distribution over higher-numbered states, find the best expected value from state 1 and round it to two decimals.	Medium4	Dynamic programmingProbability+2	No attempts yet	3s	512 MB	Judgeable
Minimum energy × delay productChoose a frequency level for each of P programs in order to minimize the total energy times delay product, including a fixed cost per frequency change.	Medium4	Dynamic programmingImplementation	No attempts yet	2s	512 MB	Judgeable
Hidden PalindromeGiven a word of at most 40 lowercase letters, find the longest palindromic subsequence obtainable by deleting letters from the front and back.	Medium4	Dynamic programmingString+2	No attempts yet	2s	512 MB	Judgeable
The nearest convenience storeGiven an undirected weighted graph with some vertices marked as homes and others as stores, pick the home whose shortest-path distance to the nearest store is smallest, breaking ties by vertex number.	Medium4	GraphShortest path+2	No attempts yet	2s	512 MB	Judgeable
Box PackingGiven box sizes in order, find the longest subsequence where each box is strictly smaller than the next, counting boxes in the pile.	Medium4	Dynamic programmingBinary search+2	No attempts yet	2s	512 MB	Judgeable
Stretch Rope (Small)N is at most 10, so enumerate subsets of bands and find the cheapest subset whose summed intervals contain L and whose total price is within M.	Medium4	Brute forceArray+2	No attempts yet	5s	512 MB	Judgeable
Safe Squares (Small)Count all axis-aligned D by D subgrids of an R by C grid that contain no monster cell.	Medium4	Dynamic programmingMatrix+2	No attempts yet	5s	512 MB	Judgeable
Resource MiningA robot walks from the top-left to the bottom-right cell of an N by M grid using only right and down moves; find the largest number of resource cells it can pass through.	Medium4	Dynamic programmingMatrix+2	No attempts yet	2s	256 MB	Judgeable
Prerequisite CoursesGiven prerequisite pairs between courses, find the earliest semester each course can be completed when unlimited courses may be taken per semester.	Medium4	GraphTopological sort+2	No attempts yet	5s	256 MB	Judgeable
Image quilting (large)Given two grayscale overlap regions of H rows and W columns, pick one column per row so adjacent rows differ by at most one, minimizing the total squared pixel difference.	Medium4	Dynamic programmingMatrix+1	No attempts yet	1s	512 MB	Judgeable
Pizza (Large)Split a tower of N into unit towers, scoring the product of the two parts at each split, and maximize the total score.	Medium4	GreedyMath+2	No attempts yet	1s	512 MB	Judgeable
Chonggang ChonggangRun a single-source shortest path from Jinseo's house, find the nearest type A and type B house, and report the closer type (A wins ties).	Medium4	Shortest pathGraph+2	No attempts yet	1s	256 MB	Judgeable
Multiples of three from 0, 1, and 2 (Large)Count N-digit numbers made only of the digits 0, 1, and 2 that are divisible by 3, with no leading zero, modulo 1e9+9.	Medium4	Dynamic programmingCombinatorics+1	No attempts yet	2s	256 MB	Judgeable
The TA is a sadist!!Given a permutation of 1 to N, find the minimum number of elements to remove so the remaining values increase from front to back.	Medium4	Dynamic programmingBinary search+2	No attempts yet	2s	256 MB	Judgeable
Milk FestivalGiven a sequence of shops selling milk types 0, 1, 2, find the longest subsequence whose values cycle 0,1,2,0,1,2,... in order.	Medium4	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Frog LeapsFind the minimum sum of squared jump distances to travel from the first stop to the last, given sorted positions.	Medium4	GreedyDynamic programming+1	No attempts yet	2s	512 MB	Judgeable
Irrational DivisionTwo players alternately cut whole columns off the west and rows off the south of a p by q chessboard chocolate; compute the optimal final score difference.	Medium4	Game theoryDynamic programming	No attempts yet	2s	512 MB	Judgeable
Counting pathsCount paths from the top-left to the bottom-right of a grid, moving only right or down and avoiding obstacle cells, modulo 10^9 + 7.	Medium4	Dynamic programmingMatrix	No attempts yet	2s	512 MB	Judgeable
Secret of Chocolate PolesCount sequences of dark and white chocolate disks, each 1 cm thick except dark thick disks at k cm, alternating colors, starting and ending dark, with total thickness at most l.	Medium4	Dynamic programmingCombinatorics	No attempts yet	1s	512 MB	Judgeable
Maximum of A[j]-A[i]+A[l]-A[k]Given an array, choose four increasing indices i<j<k<l maximizing A[j]-A[i]+A[l]-A[k].	Medium4	Dynamic programmingArray+1	No attempts yet	2s	512 MB	Judgeable
Range Digit SumSum the decimal digits of every integer from L to U, inclusive, where U can reach two billion.	Medium5	MathDynamic programming+1	No attempts yet	2s	128 MB	Judgeable
Unknown SentencePartition a sentence into segments that are anagrams of given words, minimizing total letters moved from their original word positions.	Medium5	Dynamic programmingString+1	No attempts yet	2s	128 MB	Judgeable
HotelGiven advertising costs and customer gains for up to 20 cities with unlimited repeats, find the minimum total cost to gain at least C new customers.	Medium5	Dynamic programmingMath	No attempts yet	2s	128 MB	Judgeable
PrefixGiven up to 50 words, find the largest subset where no word is a prefix of another, using a trie and tree DP.	Medium5	TrieDynamic programming+2	No attempts yet	2s	128 MB	Judgeable
Solving ProblemsGiven N interest values and a rule to move forward by 1 or 2 steps starting at problem 1, find the minimum number of problems solved before the range of solved values reaches at least V.	Medium5	Dynamic programmingGraph+2	No attempts yet	2s	128 MB	Judgeable
Tangled Electric WiresGiven a matching between left and right poles, find the minimum number of wires to cut so no two remaining wires cross, which reduces to computing N minus the longest increasing subsequence.	Medium5	Dynamic programmingBinary search+1	No attempts yet	1s	128 MB	Judgeable
Array ValueFind a path from top-left to bottom-right of an N by N grid, avoiding zero cells, that minimizes the trailing zeros in the product of visited values.	Medium5	Dynamic programmingMath+2	No attempts yet	2s	128 MB	Judgeable
Substring Picking GamePlayers alternately subtract a value formed by a proper substring of the current number's digits, and you must find the smallest first move that forces a win, or -1 if none exists.	Medium5	Game theoryDynamic programming+2	No attempts yet	2s	256 MB	Judgeable
New Year PartyPick a maximum-score guest list from a company tree so no employee and their direct manager both attend, computed with and without the root.	Medium5	Dynamic programmingTree+1	No attempts yet	2s	128 MB	Judgeable
Making the Best TeamChoose 15 players for white and 15 for black from a list of up to 1000 players to maximize the total ability sum.	Medium5	Dynamic programmingGreedy+1	No attempts yet	1s	128 MB	Judgeable
Captain DasomGiven N cannonballs, find the minimum number of tetrahedral-number piles whose sizes sum exactly to N using unbounded coin-change style DP.	Medium5	Dynamic programmingMath+1	No attempts yet	2s	128 MB	Judgeable
Summit Handshakes 2Given N seats around a round table, count the ways N representatives can pair up with non-crossing handshake segments, modulo 987654321.	Medium5	Dynamic programmingCombinatorics+1	No attempts yet	2s	128 MB	Judgeable
Number GameGiven a set of numbers including 1 and a limit K, find the first integer that cannot be formed using at most K chosen numbers, then decide the game winner by turn parity.	Medium5	Dynamic programmingMath+1	No attempts yet	2s	128 MB	Judgeable
Making a PalindromeFind the minimum number of integers to insert into a sequence so it becomes a palindrome, using interval or LCS-based dynamic programming.	Medium5	Dynamic programmingArray+1	No attempts yet	2s	128 MB	Judgeable
TilingCount the number of ways to tile a 2×n rectangle using 2×1 and 2×2 tiles for multiple values of n up to 250.	Medium5	Dynamic programmingMath+1	No attempts yet	1s	128 MB	Judgeable
Sorting the BookshelfFind the minimum number of single-book relocations needed to sort a permutation of N books into increasing order.	Medium5	Dynamic programmingArray+1	No attempts yet	2s	128 MB	Judgeable
HighwayGiven a directed graph with edge lengths and tolls, find the minimum length path from city 1 to city N whose total toll does not exceed a budget K.	Medium5	Dynamic programmingGraph+1	No attempts yet	2s	128 MB	Judgeable
Word ExtensionGiven a dictionary and a starting 3-letter word, find the longest word reachable by repeatedly inserting one letter such that each intermediate word exists in the dictionary.	Medium5	Dynamic programmingString+1	No attempts yet	2s	128 MB	Judgeable
Coin DistributionGiven several coin denominations with counts, decide for three test cases whether the coins can be split into two subsets of equal total value.	Medium5	Dynamic programmingArray	No attempts yet	2s	128 MB	Judgeable
CheersGiven N people around a circle each drinking a cola brand, find the maximum number of non-crossing pairs connecting people with the same brand.	Medium5	Dynamic programmingIntervals	No attempts yet	2s	128 MB	Judgeable
Jump Jump ChampionshipGiven an array, find the longest strictly increasing subsequence and output its length plus the indices of one such subsequence.	Medium5	Dynamic programmingBinary search+1	No attempts yet	2s	128 MB	Judgeable
Relay RaceGiven N runners in fixed order each running 1 to 3 consecutive days, find the day-count assignment summing to exactly D that maximizes total distance, or -1 if invalid.	Medium5	Dynamic programming	No attempts yet	2s	128 MB	Judgeable
Traveling Salesperson TourFind the minimum cost Hamiltonian cycle in a directed graph with up to 16 cities using bitmask dynamic programming.	Medium5	Dynamic programmingBit manipulation+1	No attempts yet	1s	128 MB	Judgeable
Bug on a TreeGiven a tree with fruit values on vertices, find the maximum sum path (simple path) and its smallest-numbered starting endpoint.	Medium5	TreeDynamic programming+1	No attempts yet	2s	128 MB	Judgeable
Wine TastingPick numbers from a sequence maximizing sum while never selecting three consecutive elements.	Medium5	Dynamic programming	No attempts yet	2s	128 MB	Judgeable
In-Flight Meal TripFind the maximum-score path from city 1 to city N using at most M cities, moving only to strictly increasing city numbers along available flights.	Medium5	Dynamic programmingGraph	No attempts yet	2s	128 MB	Judgeable
Mountain BikeFind the minimum travel time from top-left to bottom-right of a grid where each move's duration depends on cumulative speed changes from height differences, solvable via Dijkstra with speed encoded as exponent sums.	Medium5	Shortest pathGraph+1	No attempts yet	2s	128 MB	Judgeable