The classic Fibonacci sequence mentioned in the previous article is a type of one-dimensional dynamic programming. One-dimensional DP is easy to identify—it involves only one relevant attribute (superficially, a single numeric value). Besides the Fibonacci sequence, there are other common or classic one-dimensional DP problems. This article will further introduce dynamic programming through some of these problems.
You are given an integer array cost where cost[i] is the cost of climbing to the top from the ith step. Once you pay this cost, you can choose to climb one or two steps up.
You can start climbing from either step 0 or step 1.
Calculate and return the minimum cost to reach the top of the stairs.
This problem is an excellent DP example because it shows how to make non-obvious recursion explicit. The core of learning DP thinking is finding the smallest subproblems in recursion.
As you may have noticed, unlike the Fibonacci sequence, the problem description does not have obvious recursion. However, if we rephrase the problem:
Start descending stairs from the nth step. You can go down 1 or 2 steps at a time. Each descent requires paying the cost of the target step. Finally, you can reach step 1 or step 0. Which path (to step 1 or step 0) has the minimum total cost?
Now let’s analyze it using the four-step framework:
From the description, to minimize the total cost, each subsequent descent must have the minimum possible cost. This is the relationship between base cases.
The subproblem is clear: when descending one step, should you go down 1 or 2 steps? The choice depends on the cost of the two possible target steps. Just like the Fibonacci sequence, we can continuously determine which option has the lower cost—the minimum total cost is the combination of the minimum costs of each subproblem (Fibonacci proceeds forward; this problem proceeds backward). Now the problem becomes familiar, and writing code becomes straightforward.
The recursive structure can be implemented with a loop or recursive function calls. However, as mentioned in the previous article, loops are faster.
Visually, this problem forms a tree—since we choose between two options (descend 1 or 2 steps), there must be no cycles.
The “one-dimensional” nature is reflected in the use of a one-dimensional array (just like the Fibonacci sequence uses a one-dimensional array).
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
int j = n - 1; // Target position for descending stairs (cost is associated with the target step)
// These two lines prevent out-of-bounds access to the vector
int dp[n + 2];
dp[n] = dp[n + 1] = 0;
while (j >= 0) {
// Choose the cheaper option: descend 1 step or 2 steps?
if (dp[j + 1] < dp[j + 2]) {
dp[j] = cost[j] + dp[j + 1];
} else {
dp[j] = cost[j] + dp[j + 2];
}
j--;
}
// Determine which starting point (step 0 or step 1) has the minimum total cost
return dp[0] < dp[1] ? dp[0] : dp[1];
}
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Many people’s explanations of this problem are quite misleading. They explain the solution in a “simple” way but jump directly to an iterative implementation when writing code. This is not ideal because it fails to train the ability to analyze problems and derive solutions. In the end, you can only accumulate experience through a large number of problems and may eventually solve new ones.
Let’s analyze it using the four-step framework:
The relationship between base cases is straightforward: you cannot rob adjacent houses. The subproblem is defined as: after robbing a house, you must skip at least one house before robbing again. Alternatively, you can skip at most two houses—skipping three houses would mean you could have robbed the middle one.
The key is how to recursive this problem.
The runtime of DP solutions is not as concise as the solutions themselves. This is probably the cost of solving difficult problems. So don’t always think about the fastest method first—find the recursive approach, then optimize.
In the previous problem, we considered starting from step 0 or step 1. Here, we need to consider the starting scenarios: starting from the first house or the second house (starting from the third house still allows robbing the first house). The next robbery must skip at least one house. For example, if you start from the first house, the next possible robberies are houses 3 to n. Choosing between starting from the first or second house depends on the maximum value of the robbery route. What is this maximum value? In other words, how to find the maximum?
Check each possibility. Assume you start from the first house: the next robbery can only be houses 3 or 4, giving a maximum stolen value up to that point before moving to house 5. The next robberies would be houses 5 and 6, and so on until the last two houses, where you get the maximum route value. This is recursion.
Similarly, this tree-like graph can be solved with topological sort—there are no cycles. Now let’s write the code.
int rob(vector<int>& num) {
int n = num.size();
if (n == 0) return 0;
// Stores the maximum value after robbing the first (i-1) houses; no need to handle the case of only one house separately
vector<int> result(n + 1, 0);
result[1] = num[0];
// Start from the third house
// (As mentioned earlier, the starting point can only be the first or second house; the next robbery starts from the third house, indexed as 2)
for (int i = 2; i <= n; i++) {
// The stolen value is the maximum of the two options:
/* Using the example above:
The total stolen value for the third house is either:
1. The maximum value from robbing the first two houses (skipping the third), or
2. The maximum value from robbing the first house plus the third house (skipping the second)
Choose the maximum of these two.
*/
result[i] = max(result[i - 1], result[i - 2] + num[i - 1]);
}
return result[n];
}
You may wonder why we consider the case where we don’t rob a house. This is a technical choice—directly implementing the analyzed scenario makes it difficult to handle boundary cases, leading to potential out-of-bounds errors.
After these examples, you may have noticed that—ignoring recursion—converting to a for loop always requires an additional array to store intermediate results. This array essentially saves the return values of recursive calls in order. This is the fundamental principle of converting recursion to iteration.
The next article plans to cover two-dimensional DP problems. Later, I may share some interesting DP problems, as I found a DP book with really engaging examples.
I hope these will help someone in need~