Palindrome Partitioning Minimum Cuts
Given a string, return the minimum number of cuts needed such that every substring in the partition is a palindrome.
Egg Drop Puzzle
Given k eggs and n floors, compute the minimum number of attempts required in the worst case to find the highest safe floor.
Paint House Colors
Given a cost matrix, compute the minimum total cost to paint all houses with no two adjacent houses having the same color.
Buy Sell Stock with Cooldown (DP)
Given daily stock prices, compute the maximum profit you can achieve if you must wait one day after selling before buying again.
Longest Arithmetic Subsequence
Given a list of integers, return the length of the longest arithmetic subsequence (constant difference) within it.
Create Maximum Number
Given two arrays of digits and an integer k, merge them to form the largest number of length k.
Shortest Unsorted Continuous Subarray
Given an array of integers, return the length of the shortest contiguous subarray whose sorting makes the whole array sorted.
Ugly Number II
Given an integer n, return the nth ugly number using an efficient dynamic programming approach.
Unique Paths in a Grid
Count distinct paths in an m x n grid moving only down or right.
Cherry Pickup Maximum
Given a grid with cherries, find the maximum cherries you can collect using two paths from top-left to bottom-right.
Maximal square matrix
Given a 2D binary matrix of 0s and 1s, find the side length of the largest square containing only 1s.
Minimum Falling Path Sum
Compute the minimum falling path sum in an n x n matrix by moving down or diagonally each step.
Derangement count
Implement a function to count derangements of n items using the classic recurrence.
Shortest Common Supersequence
Given two strings, return any shortest supersequence that contains both as subsequences.
Interleaving string
Given three strings s1, s2, and s3, check if s3 is formed by interleaving s1 and s2 while preserving the order of each input string.
Count subsets with sum
Given a list of integers and a target sum, count how many subsets of the list sum to the target.
Matrix Chain Multiplication
Given a list of matrix dimensions, compute the minimum multiplication cost using dynamic programming.
Target sum assignments
Given a list of integers and a target, count how many ways to assign + or - to each number so the total equals the target.
Subset Sum Exists
Given a list of positive integers and a target sum, return whether some subset adds up exactly to the target.
Tiling dominoes count
Given a 2 x n board, count the distinct tilings using 2 x 1 dominoes.
Delete and Earn
Given an array of integers, find the maximum points you can earn by repeatedly deleting a number and all its adjacent values.
Split Array Largest Sum
Minimize the largest sum among k contiguous subarrays using dynamic programming.
Maximal rectangle in matrix
Given a matrix of 0s and 1s, compute the area of the largest rectangle consisting only of 1s.
Minimum Path Sum Matrix
Implement a function that computes the minimum path sum from the top-left to the bottom-right of a grid moving only right or down.
Showing 25–48 of 49 challenges · Dynamic Programming
Dynamic Programming — Python coding challenges
What you will find here
This page lists dynamic programming challenges — real Python problems you solve in the browser IDE with instant test feedback. Each challenge includes a clear brief, starter code, and automated checks.
Challenges vs tutorials and quizzes
Challenges test what you can build under constraints. For guided teaching, use our Python tutorials. For quick checks, try quizzes or copy snippets from code samples.