An algorithm design method that splits a problem into smaller subproblems and records their answers in a table for reuse, avoiding repeated computation of the same thing. It is used for the knapsack problem, minimum-coin change, the longest common subsequence, shortest paths and more.
Japanese name: 動的計画法
Dynamic programming appears in 3 practice questions across 1 topic, including Data Structures and Algorithms.
Computing Fibonacci numbers directly from fib(n) = fib(n−1) + fib(n−2) with recursion recomputes the same values again and again, so the number of calls grows exponentially (about 2.69 million for fib(30)). Dynamic programming records the answer to each subproblem once it is found and simply looks it up afterward, so fib(n) takes work proportional to n. It applies when the optimal solution of a large problem can be built from optimal solutions of smaller subproblems (optimal substructure) and the same subproblems appear many times (overlapping subproblems).
There are two ways to implement it: memoization (top-down), which keeps the recursive form but remembers computed results, and the bottom-up approach, which fills a table starting from the smallest subproblems. For the 0/1 knapsack problem, for example, the table holds “the maximum value achievable using items up to i within capacity c” and is filled by taking the larger of including or excluding each item. For n items and capacity W, this takes O(nW). The minimum-coin problem can likewise be solved by tabulating the minimum number of coins for each amount from 0 up to the target.
A greedy algorithm simply picks the choice that looks best at each moment and moves on, so it is fast but not optimal for some problems. Paying 8 yen with 1-, 4- and 6-yen coins, the greedy algorithm uses three coins, 6 + 1 + 1, while dynamic programming finds two, 4 + 4. Dynamic programming is widely used, for example for edit distance and the longest common subsequence of strings (as in the diff command), DNA sequence alignment, the Viterbi algorithm in speech recognition, and the Floyd-Warshall algorithm for shortest paths between all pairs of vertices.
Answer: C. 15
Let C(n) be the number of calls for fib(n). Then C(0) = C(1) = 1 and C(n) = 1 + C(n−1) + C(n−2), so C(2) = 3, C(3) = 5, C(4) = 9 and C(5) = 15. Because the same values are recomputed again and again, the count grows exponentially with n; fib(30) makes about 2.69 million calls. With memoization (a form of dynamic programming), which stores computed values in a table, only the six values fib(0) to fib(5) are computed and the calls drop to 9 (2n − 1). 6 is the number of distinct arguments, and 9 is the number of calls with memoization.
Answer: B. The greedy algorithm uses 3 coins and misses the minimum of 2
The greedy algorithm first takes one 6-yen coin and pays the remaining 2 yen with two 1-yen coins, for 3 coins. But two 4-yen coins pay it with just 2. Because a greedy algorithm only accumulates the choice that looks best at each moment, it is not optimal for some coin systems. Dynamic programming, which fills in a table of the minimum number of coins for every amount from 0 to 8 yen in increasing order, always finds the minimum. For coin systems such as Japan's 1, 5, 10, 50, 100 and 500 yen, the greedy algorithm always gives the minimum.
Both split a problem into subproblems, but in divide-and-conquer algorithms such as merge sort the subproblems do not overlap, so there is no need to record answers. Dynamic programming differs in recording and reusing answers when the same subproblems appear many times.
It needs memory and work in proportion to the size of the table. The O(nW) of the knapsack problem is proportional to the value of the capacity W, so it becomes impractical when W is very large. Memory can be reduced by recording only what is needed or keeping only the previous row of the table.
With memoization (a form of dynamic programming), which stores computed values in a table, only the six values fib(0) to fib(5) are computed and the calls drop to 9 (2n − 1).
A function fib(n) for Fibonacci numbers is defined recursiv…Dynamic programming, which fills in a table of the minimum number of coins for every amount from 0 to 8 yen in increasing order, always finds the minimum.
You pay 8 yen with coins of 1 yen, 4 yen and 6 yen. Which c…Dynamic programming updates a table of the best value achievable within each capacity c item by item, and finds the optimum in O(nW) for n items and capacity W.
A knapsack with capacity 8 is filled with items chosen from…As an Amazon Associate I earn from qualifying purchases.
Greedy algorithm Argument Binary heap Binary search Binary search tree Breadth-first search Depth-first search Dijkstra's algorithm Hash table Linked list