Card 1 / 10
Dynamic programming solves a problem by combining answers to smaller
subproblems, computing each distinct subproblem once and reusing the stored
result. Implement minOperationsToOne: reduce n to 1 using subtract 1,
divide by 2, or divide by 3, in as few operations as possible.
n |
result | one optimal path | why included |
|---|---|---|---|
1 |
0 |
1 |
base case |
6 |
2 |
6 → 3 → 1 |
division transitions |
10 |
3 |
10 → 9 → 3 → 1 |
defeats "divide whenever possible" |
dp[i] = fewest operations to reduce i to 1. Every i can reach i - 1;
check divisibility before using i / 2 or i / 3.
Build up from dp[1] = 0: dp[i] = 1 + min(dp[i-1], dp[i/2] if divisible, dp[i/3] if divisible). Greedy halving costs 4 on 10
(10 → 5 → 4 → 2 → 1); the table finds 10 → 9 → 3 → 1.
// Minimum number of operations to reduce n (n >= 1) to 1.
// Allowed operations: subtract 1; divide by 2 (only if divisible);
// divide by 3 (only if divisible).
int minOperationsToOne(int n) {
std::vector<int> dp(n + 1, 0);
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 2 == 0) dp[i] = std::min(dp[i], dp[i / 2] + 1);
if (i % 3 == 0) dp[i] = std::min(dp[i], dp[i / 3] + 1);
}
return dp[n];
}Card 2 / 10
Overlapping subproblems occur when different recursive branches can reach the same argument state. When they can, memoize — keyed by the smallest set of arguments that identifies the subproblem.