Dynamic Programming interview questions

Maximize the value packed into a weight-limited knapsack when each item can be taken at most once — the classic 0/1 dynamic-programming table.

Compute the minimum number of insertions, deletions, and replacements to turn one string into another — the Levenshtein distance via a 2D dynamic-programming table.

Find the area of the largest all-ones square in a binary matrix, where each cell's square size is one more than the smallest of its top, left, and top-left neighbors.

Find the cheapest path from the top-left to the bottom-right of a grid, moving only right or down, by summing each cell with the smaller of the two ways to reach it.

Decide whether an array can split into two subsets with equal sums — a subset-sum dynamic-programming problem over half the total.

Implement a function that decides whether a string can be broken into a sequence of words from a given dictionary.

Decide whether a string matches a pattern containing `?` (any single character) and `*` (any sequence) — a two-dimensional dynamic-programming match over string and pattern.