Introduction
Dynamic programming is a common type of problem in coding interviews. Mastering it is crucial.
NetEase Problem
Little Q and Dr. Niu are singing a song together. This song consists of n notes, each represented by a positive integer. Each note must be sung by either Little Q or Dr. Niu. The difficulty of singing a series of notes equals the sum of the absolute differences between all adjacent notes. For example, if a sequence of notes is 8, 8, 13, 12, then its difficulty is |8 - 8| + |13 - 8| + |12 - 13| = 6 (where || represents absolute value). Now we need to distribute these n notes between Little Q and Dr. Niu to minimize the sum of their singing difficulties. Calculate the minimum possible total difficulty. As shown in the example: Little Q chooses to sing {5, 6} with difficulty 1, Dr. Niu chooses to sing {1, 2, 1} with difficulty 2, the sum of difficulties is 3, which is the minimum possible difficulty.
Greedy Approach (Incorrect)
Sort all the numbers and use the largest difference between two numbers as a dividing point. Assign the lower half to Little Q and the upper half to Dr. Niu, then calculate the result. This approach passes 60% of the test cases. If time is limited or you don’t know how to solve it optimally, you can use this approach.
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> nums;
for(int i=0;i<n;i++)
{
int num;
cin >> num;
nums.push_back(num);
}
vector<int> nums_sort(nums.begin(), nums.end());
sort(nums_sort.begin(), nums_sort.end());
int max_gap = 0;
auto max_gap_it = nums_sort.begin();
for(auto it=nums_sort.begin(); it!=nums_sort.end()-1; it++){
if(*(it+1) - *it > max_gap){
max_gap = *(it+1) - *it;
max_gap_it = it;
}
}
int max_gap_num = *max_gap_it;
int ret = 0;
int last_1 = -1;
int last_2 = -1;
for(auto it = nums.begin(); it!=nums.end(); it++){
if(*it <= max_gap_num){
if(last_1 != -1){
ret += abs(*it - last_1);
}
last_1 = *it;
}
else{
if(last_2 != -1){
ret += abs(*it - last_2);
}
last_2 = *it;
}
}
cout << ret;
}
Thinking About Dynamic Programming
Since I don’t know much about dynamic programming, let’s start with the coin change problem.
- Coin Change Problem
The core of dynamic programming lies in breaking down the problem and recursively combining subproblems to solve the original problem.
For example, suppose we have coins with denominations of 1, 3, and 5, and we want to make change for 11 using the minimum number of coins. If you’re human, you might say, “I can easily see that two 5-coins and one 1-coin, for a total of 3 coins, is optimal.” Let’s try a different example: what about making change for 237? You might say, “I’ll first use 5-value coins to make 200, then find the optimal combination for the remaining 37.” This method assumes that splitting 237 into two parts and finding the optimal solution for each part will yield the global optimal solution. If that were always true, there would be no problem. But the issue is with splitting into 200 and 37 - there’s no proof that this is an effective split. Dynamic programming is built on effective partitioning.
Both divide-and-conquer algorithms and dynamic programming are based on partitioning. The difference is that dynamic programming involves state transitions, while divide-and-conquer doesn’t. Divide-and-conquer can decompose from top to bottom, while dynamic programming usually builds from bottom to top.
Dynamic programming involves two dimensions. The first dimension is usually related to the scale of the problem, and the second dimension needs to be extracted from the problem. In this coin change problem, the second dimension is the allowed coins: for example, allowing only 1-value coins, allowing 1 and 3-value coins, or allowing 1, 3, and 5-value coins. We denote this with index 1, 2, 3, and use j to represent this variable. If we use i to represent the current problem scale (237), then we want to find c[i][j], which is c[237][3]. For this problem, we can make two assumptions: first, the optimal solution uses at least one 5-value coin; second, the optimal solution uses no 5-value coins. For the second assumption, c[237][3] = c[237][2], because if we don’t use any 5-value coins, then the optimal solution should be the same as using only 1 and 3-value coins. For the first assumption, since the solution must contain at least one 5-value coin, after removing this 5-value coin, we have 232 left. Since c[237][3] is the optimal value for making change for 237 using coins of values 1, 3, and 5, and it must contain at least one 5-value coin, the remaining coins that make up 232 must also be in an optimal state (if the subproblem weren’t optimal, that is, if there were a better solution for making 232 within the solution for 237, then the solution for 237 wouldn’t be optimal, contradicting our assumption). So c[232][3] = c[237][3] - 1.
This allows us to derive: c[i][j] = c[i][j-1] (Assumption 1) c[i][j] = c[i-value of denomination j][j] + 1 (Assumption 2) When written in the form of min(), this becomes the familiar state transition equation.
We ultimately want to find c[11][5], and we work from the c[0][0] state towards the bottom right corner of the table to derive the answer.
- Two-Person Singing Difficulty Problem https://www.nowcoder.com/questionTerminal/fddf64d5757e41ec93f3ef0c0a10b891
We must remember:
The optimal solution to the problem is not necessarily the value in the bottom-right corner of the state matrix
We must always remember that the bottom-right cell of the state matrix is not necessarily the direct optimal solution. Thinking this way often leads to confusion. Instead, we should think that the matrix indices i and j are definitely related to the two dimensions of the problem, but dp[i][j] does not necessarily represent the value of the optimal solution.
For example, in this problem, we need to find the optimal difficulty coefficient. If dp[i_max][j_max] were the optimal difficulty coefficient, what would i and j index? This is unsolvable. Looking at it differently, what exactly is the optimal difficulty coefficient? Since state transitions exist, the optimal state must be the minimum value obtained from multiple states. What does i represent? If i represents the current note being sung, what does j represent? J can only represent the note sung by the other person. Then, in the optimal state, how many situations are there? We calculate the optimal value from these situations. In the optimal state, one person must be singing the last note, while the other person might not be singing any note, might be singing the first note, might be singing the second note… might be singing the second-to-last note. We calculate the minimum value of all these situations to find the optimal solution.
Another question is whether i and j should be assigned to specific people. If i represents Little Q’s notes and j represents Dr. Niu’s notes, then the matrix would be symmetric, and we’d be calculating half of the content redundantly. Actually, we don’t care who is singing what, because they are equivalent. We can only think of it as one person currently singing up to position i, and the other person last sang up to position j.
What states can c[i][j] transition from? For example, if one person has sung up to the 6th note, and the other person last sang up to the 3rd note, if the current total difficulty is minimal, then: The 6th, 5th, and 4th notes are all sung by the first person. This is because the second person has only sung up to the 3rd note and cannot sing later notes. So c[6][3] = c[5][3] + difficulty difference between notes 5 and 6 = c[4][3] + difficulty difference between notes 4 and 5. But how is c[4][3] transitioned? If the first person has sung up to the 4th note, and the other person has sung up to the 3rd note, this means the first person interrupted the second person’s singing. Since we don’t know from where the first person jumped to the 4th note, we assume all possible notes. If they jumped from the 2nd note, then it’s c[3][2] + difference between notes 3 and 4. If they jumped from the 1st note, then it’s c[3][1] + difference between notes 1 and 4. If they didn’t jump, then it’s c[3][0] + difference between notes 0 and 4. Since the last note sung by the second person is always less than the note being sung by the first person, we don’t need to consider the case where j >= i.
Based on this, here’s the code:
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <array>
using namespace std;
vector<int> nums;
array<array<int, 2100>, 2100> dp;
/* Calculate the difficulty between two notes. Note that the index of the first note in the input data is 0, so there's a difference of 1. If the starting note is 0, it means it's the first time singing, so no additional difficulty */
int diffcult(int s, int e)
{
if(s == 0) return 0;
// printf("diffcult %d %d to %d %d is %d \n", s,nums[s-1], e,nums[e-1], abs(nums[e-1] - nums[s-1]));
return abs(nums[e-1] - nums[s-1]);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
nums.push_back(num);
}
/* Start from 0 and consider all notes. The worst case for the first person is not singing at all, in which case j also doesn't sing, and we continue */
for (int i = 0; i <= n; i++)
{
/* Also start from 0 here, because in the worst case, the first person doesn't sing at all, which is position 0 */
for (int j = 0; j <= n; j++)
{
/* Don't consider later cases. This could also be incorporated into the range limitation above */
if (j >= i)
continue;
/* In the general case, for example, if the first person is singing the 6th note and the second person is singing the 3rd note, it clearly transitions from dp[5][3] */
if (j + 1 < i)
{
dp[i][j] = dp[i - 1][j] + diffcult(i - 1, i);
}
/* Otherwise, if the second person just finished singing and the first person took over, the first person's note could be jumped from earlier */
if (j + 1 == i)
{
/* k represents which note i jumped from */
int min_cost = -1;
for (int k = 0; k < j; k++)
{
int cost = dp[j][k] + diffcult(k, j + 1);
/* Only record the minimum jump difficulty */
if(min_cost == -1 || min_cost > cost){
min_cost = cost;
}
}
if(min_cost == -1) min_cost = 0;
dp[i][j] = min_cost;
}
// for(int a=0;a<=n;a++){
// for(int b=0;b<=n;b++){
// if(a==i && b == j){
// printf("\t【%d】", dp[a][b]);
// }
// else printf("\t%d", dp[a][b]);
// }
// // printf("\n");
// }
// printf("\n");
}
}
int min_cost = -1;
for(int j=0;j<n;j++){
if(min_cost == -1 || min_cost > dp[n][j]){
min_cost = dp[n][j];
}
}
printf("%d", min_cost);
}
- Longest Palindromic Substring Problem https://leetcode.com/problems/longest-palindromic-substring/description/
I now understand why dynamic programming is presented in this way. The key point of two-dimensional dynamic programming problems is:
The planar expansion of linear growth problems
For example, in the coin change problem, expanding the second dimension represents making change with the current coin type. In the singing problem, it’s the minimum difficulty when singing up to the current position while the other person last sang at a certain position. For the longest palindromic substring, it becomes the starting position.
In the longest palindromic substring, i represents the starting character, and j represents the ending character of the substring. When i is the starting character and j is the ending character, we have the answer to the problem.
For the smallest subproblem, which is a single character, its length is 1. For longer strings, if the characters at both ends are different, then it equals the smaller value of removing either the right or left character. If the characters at both ends are the same, then it equals the value of the substring with both ends removed plus 2.
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp;
dp.resize(s.size() + 1);
for (int i = 0; i < s.size() + 1; i++)
{
dp[i].resize(s.size() + 1);
}
int len = s.size();
for(int t=0;t<len;t++){
for(int j=t; j<len;j++){
int i = j-t;
if(i==j){
dp[i][j] = 1;
}
else if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1] + 2;
}
else{
if(dp[i+1][j]> dp[i][j-1]){
dp[i][j] = dp[i+1][j];
}
else{
dp[i][j] = dp[i][j-1];
}
}
}
}
return dp[0][len-1];
}
};