Introduction
Today, we will discuss DP, which stands for Dynamic Programming. There are many types of DP, such as Knapsack DP, Digit DP, Tree DP, and Bitmask DP… These are all advanced skills that I will share with you in the future. For today, let’s simply understand the basics of DP.
01
Dynamic Programming Concepts
Dynamic Programming (DP) is a branch of operations research that focuses on optimizing decision-making processes. The applications of dynamic programming are extremely broad, including fields such as engineering technology, economics, industrial production, military, and automation control. It has achieved significant results in problems such as the Knapsack problem, production management problems, financial management problems, resource allocation problems, the shortest path problem, and complex system reliability issues.
Dynamic programming algorithms are typically used to solve problems that exhibit certain optimal properties. In these types of problems, there may be many feasible solutions. Each solution corresponds to a value, and we aim to find the solution with the optimal value. Problems suitable for dynamic programming often have subproblems that are not independent of each other. If we use the divide-and-conquer method to solve such problems, the number of subproblems generated can be too large, and some subproblems may be computed multiple times. If we can store the answers to solved subproblems and retrieve them when needed, we can avoid a lot of redundant calculations and save time. We can use a table to record the answers to all solved subproblems. Regardless of whether the subproblem is used later, as long as it has been computed, we will fill its result into the table.
Dynamic programming emphasizes a step-by-step approach, calculating everything, whether useful or not (within time and space complexity limits).
02
State Transition Equations
This is a type of equation that can be expressed either recursively or directly, such as:
Fibonacci sequence recurrence formula: Xi=Xi-1+Xi-2. Of course, with a little derivation, we can obtain a formula that does not require recursion, which we call the general term formula. The general term formula also belongs to the category of state transition equations, such as: Fibonacci sequence general term formula: Xi=(1/√5)*{[(1+√5)/2]^i+[(1-√5)/2]^i}. This can be proven using simple methods like undetermined coefficients, recursion, or linear algebra.03
Example Problems
Let’s take a Fibonacci number as an example:
Example 1: Input n, output the nth Fibonacci number.
#include<bits/stdc++.h>using namespace std;typedef long long ll;ll dp[100009];// Dynamic programming array, where the i-th element represents the i-th Fibonacci numberll x;int main() { cin >> x; dp[1] = 1, dp[2] = 1;for (int i = 3; i <= x; i++) { dp[i] = dp[i - 1] + dp[i - 2];// State transition equation } cout << dp[x];return 0;}Example 2: There are n steps, and you can take either 1 step or 3 steps at a time. Find how many ways there are to exactly reach the nth step.
#include<bits/stdc++.h>using namespace std;typedef long long ll;ll dp[100009];// Dynamic programming array, where the i-th element represents the number of ways to reach the i-th stepll x;int main() { cin >> x; dp[1] = 1, dp[2] = 1, dp[3] = 2;for (int i = 4; i <= x; i++) { dp[i] = dp[i - 1] + dp[i - 3];// State transition equation } cout << dp[x];return 0;} This is a classic stair climbing problem.Today, we have only briefly introduced the topic. Stay tuned for the second part on dynamic programming: Knapsack DP.
See you next time,ヾ(￣▽￣)Bye~Bye~
Previous quality content from our public account:
C++ Programming Beginner’s Lesson 1: Greedy Algorithm
Scratch Programming Beginner’s Lesson 1: Gravity and Rebound
An Interesting Experiment
C++ Programming Beginner’s Lesson 6: Structures