🌐 中文 English
Let’s step into the world of DP
Chapter test link:
https://leetcode.cn/problems/minimum-path-sum/description/
What is DP
dp stands for Dynamic Programming, which is translated into Chinese as 动态规划. Its core idea is to decompose the original problem into a series of overlapping subproblems, solve these subproblems step by step, and store their results to avoid redundant calculations, thereby improving algorithm efficiency. Essentially, it is an algorithmic concept that trades space for time.
The Correct Path to DP Implementation
Many people immediately think of concepts like overlapping subproblems, optimal substructure, and no aftereffects when they encounter dp. While these are important, they are not very helpful when we are just starting to learn.
The real learning and implementation path for dp should start from the most familiar recursion and progress towards dp.
Below, I will demonstrate the complete implementation thought process from recursion to dp, using a two-dimensional dp problem from leetcode as an example:
1. Start with Recursive Implementation
This is a very simple recursive implementation. I’ll directly provide the code here:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<climits>
#include<algorithm>
// Recursive processing
class Solution {
public:
int n, m;
// Push back from the endpoint
int f(vector<vector<int>>& grid, int i, int j)
{
if (i == 0 && j == 0) return grid[0][0];
int up = INT_MAX;
int left = INT_MAX;
if (i - 1 >= 0)
{
up = f(grid, i - 1, j); // Move up one step
}
if (j - 1 >= 0)
{
left = f(grid, i, j - 1); // Move left one step
}
return grid[i][j] + min(up, left);
}
int minPathSum(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
return f(grid, n - 1, m - 1);
}
};
We can see the design idea is correct, but the execution speed is very slow, so we need to optimize it with dp.
2. Implement dp with Memoization Search
I decided to use a two-dimensional dp array for dynamic programming during recursion, caching results for each grid, and using memoization search to avoid redundant calculations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<algorithm>
#include<climits>
class Solution {
public:
// Memoization search
vector<vector<int>> dp;
int n, m;
int f(vector<vector<int>>& grid, int i, int j)
{
if(dp[i][j] != -1)
{
return dp[i][j];
}
int ans;
if(i == 0 && j == 0)
{
ans = grid[0][0];
}
else
{
int up = INT_MAX, left = INT_MAX; // Ensure one side is valid when the other is invalid
if(i - 1 >= 0)
{ up = f(grid, i - 1, j); }
if(j - 1 >= 0)
{ left = f(grid, i, j - 1); }
ans = grid[i][j] + min(up, left);
}
dp[i][j] = ans; // First assignment to dp[0][0]
return ans;
}
int minPathSum(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
dp = vector<vector<int>>(n, vector<int>(m, -1));
return f(grid, n - 1, m - 1);
}
};
We can see the execution speed has improved significantly, but each recursive call incurs function call overhead, including parameter passing, stack operations, etc. Therefore, we need to continue optimizing.
3. Implement dp with Strict Position Dependency
Based on the above dp implementation idea, we can find that dp[i][j] only depends on dp[i-1][j] and dp[i][j-1]. Therefore, we can relate these dp positions and then use for loops to implement dp.
The code is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<algorithm>
#include<climits>
class Solution {
public:
int n, m;
vector<vector<int>> dp;
int minPathSum(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
if( n == 1 && m == 1)
{
return grid[0][0];
}
dp = vector<vector<int>>(n, vector<int>(m, INT_MAX)); // 0 <= grid[i][j] <= 200
dp[n - 1][m - 1] = grid[n - 1][m - 1];
for(int i = n - 1; i >= 0; --i)
{
for(int j = m - 1; j >= 0; --j)
{
if(i - 1 >= 0) dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + grid[i - 1][j]); // Move up
if(j - 1 >= 0) dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + grid[i][j - 1]); // Move left
}
}
return dp[0][0];
}
};
We can see the code becomes more concise and efficient after using strict position dependency, but its memory consumption is still high, so we can proceed to the next optimization.
4. Implement Space-Optimized dp
In the above code, we will find that dp only uses dp[i-1][j] and dp[i][j-1] in the later process. Therefore, we can use two one-dimensional dp arrays to replace the two-dimensional dp array, achieving space optimization.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Use two dp arrays to roll the two-dimensional dp, achieving space compression
#include<algorithm>
#include<climits>
class Solution {
public:
int n, m;
vector<int> dp1;
vector<int> dp2;
int minPathSum(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
if (n == 1 && m == 1)
{
return grid[0][0];
}
dp1 = vector<int>(m, INT_MAX); // 0 <= grid[i][j] <= 200
dp2 = vector<int>(m, INT_MAX);
dp1[0] = grid[0][0];
for (int i = 1; i < m; ++i) // Initialize dp1
{
dp1[i] = dp1[i - 1] + grid[0][i];
}
for (int i = 1; i < n; ++i)
{
dp2[0] = dp1[0] + grid[i][0];
for (int j = 1; j < m; ++j)
{
dp2[j] = min(dp1[j], dp2[j - 1]) + grid[i][j];
}
dp1 = dp2;
}
return dp1[m - 1];
}
};
We can see the space-optimized code consumes less storage and also saves memory consumption.
Summary
From recursion to dp, I believe this is the most authentic implementation thought process for dp. Actually, the implementation idea of dp is not difficult, but to truly master it, one needs to think more, summarize more, and practice more.
