[question brushing diary] classic questions of dynamic planning

Hello everyone , I am a Bai Chen , One is not very able to stay up late , But people who want to be more and more . If you like this article , Point a praise , Pay attention to it. Bai Chen bar ！ Your support is my biggest motivation ！

Preface

---

Reminders before watching ： This article needs some foundation of Dynamic Planning

Most methods of dynamic programming are very abstract , And it has a wide range of applications in life . The abstraction of this algorithm requires learning dynamic programming algorithm , You can't just look at the idea of the algorithm , Instead of doing questions .

therefore , Bai Chen sorted out the classic topics in dynamic programming for everyone to better master the dynamic programming algorithm , Topics range from matrix to string , The difficulty goes from easy to difficult , The degree of abstraction ranges from one dimension to two dimensions .

If you haven't been exposed to the idea of Dynamic Planning perhaps Some of the questions are really hard to understand It doesn't matter , Bai Chen will release the full analysis of dynamic programming algorithm in the near future , Among them, it focuses on the more difficult topics in dynamic planning again , Such as knapsack problem .

---

Dynamic programming classic topic

1. Fibonacci sequence

---

Original link ： Fibonacci sequence

This problem may be a problem that you have just learned C A problem I did when I was speaking , Now let's analyze this problem according to the idea of dynamic programming ：

1. What is the state of this problem ？

   That is, we need to solve / Face what , What we need to solve here is the Fibonacci number n Value of item , So we set the first n Item value is $f(n)$ , That is, the status is $f(n)$

2. What is the state transition equation ？

   Here we can analyze the state , use Where do I come from The idea of , It's easy to get $f(n)=f(n-1)+f(n-2)$ .

3. What is the initialization of state ？

   That is, what is the initial state ？

   $f(1)=1,f(2)=1$

4. Return value

   From the above, we can get that the return value is $f(n)$ .

To sum up ：

• state ：$f(k)$
• State recurrence ：$f(k)=f(k-1)+f(k-2)$
• Initial value ：$f(1)=f(2)=1$
• Return results ：$f(n)$

According to the above analysis, the specific code ：

class Solution {
    
public:
    int Fibonacci(int n) {
    
        int fib1 = 1;
        int fib2 = 1;
        int f;

        if (n == 1 || n == 2)
            return 1;

        for (int i = 3; i <= n; i++)
        {
    
            f = fib1 + fib2;

            fib2 = fib1;
            fib1 = f;
        }

        return f;
    }
};

---

2. Split words and sentences

---

Original link ： Split words and sentences

state ：
Substate ： front 1,2,3,…,n Whether a character can be successfully segmented according to the words in the dictionary

• $F(i)$ : front i Whether a character can be successfully segmented according to the words in the dictionary

State recurrence ：

• $F(i)$: true{$j < i $ && $F(j)$ && $substr[j+1,i]$ Can be found in a dictionary } OR false
• stay j Less than i in , As long as you can find one $F(j)$ by true, And from j+1 To i The characters between can be found in the dictionary , be $F(i)$ by true

Initial value ：

• For those whose initial value cannot be determined , You can introduce an empty state that does not represent the actual meaning , As the beginning of the State ;
• The value of empty state needs to ensure that the state recurrence can be carried out correctly and smoothly , What value to take can be verified by a simple example
• $F(0)=true$

Return results ： $F(n)$

class Solution {
    
public:
    bool wordBreak(string s, unordered_set<string>& dict) {
    
        if (s.empty())
            return false;
        if (dict.empty())
            return false;

        vector<bool> can_spe(s.size() + 1, false);
        //  initialization 
        can_spe[0] = true;

        for (int i = 1; i <= s.size(); i++)
        {
    
            for (int j = i - 1; j >= 0; j--)
            {
    
                //  At present  j  Characters can be separated from a dictionary , also  [j + 1, i]  When the character of is exactly the character in the dictionary 
                //  Judge as true 
                if (can_spe[j] && dict.find(s.substr(j, i - j)) != dict.end())
                {
    
                    can_spe[i] = true;
                    break;
                }
            }
        }

        return can_spe[s.size()];
    }
};

---

3. Trigonometric matrix

---

Original link ： triangle

class Solution {
    
public:
    int minimumTotal(vector<vector<int> >& triangle) {
    
        if (triangle.empty())
            return 0;

        int row = triangle.size();

        for (int i = 1; i < row; i++)
        {
    
            for (int j = 0; j <= i; j++)
            {
    
                //  initialization 
                if (j == 0)
                    triangle[i][0] = triangle[i - 1][0] + triangle[i][0];
                else if (j == i)
                    triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j];
                //  Choose to arrive  [i][j]  The minimum value of 
                else
                    triangle[i][j] = min(triangle[i - 1][j], triangle[i - 1][j - 1]) + triangle[i][j];
            }
        }
		
        int Min = triangle[row - 1][0];
		//  Traverse the last line , Select the minimum value 
        for (int j = 1; j < row; j++)
            Min = min(Min, triangle[row - 1][j]);

        return Min;
    }
};

---

4. Find the way

---

Original link ： Find the way

Law 1 ： recursive

class Solution {
    
public:

    int uniquePaths(int m, int n) {
    
        if (m == 1 || n == 1)
            return 1;

        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
};

Law two ： Dynamic programming

class Solution {
    
public:

    int uniquePaths(int m, int n) {
    
        if (m == 1 || n == 1)
            return 1;
        //  Initialize to 1
        vector<vector<int> > a(m, vector<int>(n, 1));


        for (int i = 1; i < m; i++)
        {
    
            //  arrive  [i][j]  The number of paths   be equal to   arrive [i - 1][j] And arrival [i][j - 1] The sum of the number of paths 
            for (int j = 1; j < n; j++)
                a[i][j] = a[i][j - 1] + a[i - 1][j];
        }

        return a[m - 1][n - 1];
    }
};

Law three ： Formula method

class Solution {
    
public:
    
    int uniquePaths(int m, int n) {
    
        long long ret = 1;

        for (int i = n, j = 1; j < m; i++, j++)
            ret = ret * i / j;

        return ret;
    }
};

---

5. Minimum path sum with weight

---

Original link ： Minimum path sum with weight

class Solution {
    
public:
    int minPathSum(vector<vector<int> >& grid) {
    
        int m = grid.size();
        int n = grid[0].size();
		
        // initialization 
        for (int i = 1; i < m; i++)
            grid[i][0] = grid[i - 1][0] + grid[i][0];

        for (int i = 1; i < n; i++)
            grid[0][i] = grid[0][i - 1] + grid[0][i];
		
        //  Transfer equation 
        for (int i = 1; i < m; i++)
        {
    
            for (int j = 1; j < n; j++)
                grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
        }

        return grid[m - 1][n - 1];
    }
};

---

🧂6. knapsack problem

---

Original link ： knapsack problem

class Solution {
    
public:
    int backPackII(int m, vector<int>& A, vector<int>& V) {
    
        if (A.empty() || V.empty() || m < 1)
            return 0;

        const int N = A.size() + 1;
        const int M = m + 1;
        vector<vector<int> > ret;
        ret.resize(N);
		//  initialization 
        for (int i = 0; i != N; ++i) {
    
            ret[i].resize(M, 0);
        }

        for (int i = 1; i < N; i++)
        {
    
            for (int j = 1; j < M; j++)
            {
    
                //  If the total space of the backpack is not enough i Items , Then put  i  Items and   discharge  i - 1  The situation of two items is the same 
                if (j < A[i - 1])
                    ret[i][j] = ret[i - 1][j];
                //  If there's enough room for i Items , Then it is necessary to judge whether to put , See the above analysis for details 
                else
                    ret[i][j] = max(ret[i - 1][j], ret[i - 1][j - A[i - 1]] + V[i - 1]);
            }
        }

        return ret[N - 1][m];
    }
};

optimization algorithm ：

class Solution {
    
public:
    int backPackII(int m, vector<int>& A, vector<int>& V) {
    
        if (A.empty() || V.empty() || m < 1)
            return 0;

        const int M = m + 1; //  Package capacity 
        const int N = A.size() + 1; //  Quantity of articles 
        vector<int> ret(M, 0);

        for (int i = 1; i < N; i++)
        {
    
            //  The above algorithm is calculating the i Line element , Only the second i-1 Elements of the line , Therefore, two-dimensional space can be optimized into one-dimensional space 
            //  But if it's a one-dimensional vector , Need to calculate from back to front , Because the later element update needs to rely on the previous element not updated （ Simulate the value of the upper row of a two-dimensional matrix ）
            //  And we observed , The elements of this line only need to use the elements of the previous line , So from front to back , It's the same from back to front 
            //  And the subscript of the element in the previous line will not exceed the subscript of the element in this line 
            for (int j = m; j >= 0; j--)
            {
    
                if (j >= A[i - 1])
                    ret[j] = max(ret[j], ret[j - A[i - 1]] + V[i - 1]);
            }
        }

        return ret[m];
    }
};

---

7. Split palindrome string

---

Original link ： Split palindrome string

state ：
Substate ： To the first 1,2,3,…,n The minimum number of divisions required for a character

• $F(i)$: To the first i The minimum number of divisions required for a character

State recurrence ：

• $F(i)=minF(i),1+F(j)$, where j < i && j + 1 To i It's a palindrome string
• The above formula means if from j+1 To i It is a palindrome string , And already know from the 1 Character to character j Minimum number of cuts of characters , Then just cut it again , You can guarantee 1–>j, j+1–>i Are palindromes .

initialization ：

• $F(i)=i-1$
• The above formula means to i The maximum number of divisions required for a character , For example, a single character only needs to be cut 0 Time , Because the list characters are palindromes ,2 Characters, max 1 Time ,3 individual 2 Time …

Return results ：

• $F(n)$

class Solution {
    
public:
    //  Determine whether it is a palindrome string 
    bool isPal(string& s, int left, int right)
    {
    
        while (left < right)
        {
    
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }

        return true;
    }
    int minCut(string s) {
    
        if (s.empty())
            return 0;
        int len = s.size();
        int* ret = new int[len + 1];
        //  One is long for  i  String , Form palindrome string , At most, it needs to be cut  i - 1 The knife 
        for (int i = 0; i <= len; ++i)
        {
    
            //  Initialize to the maximum number of times each string can be divided 
            ret[i] = i - 1;
        }

        for (int i = 2; i <= len; ++i)
        {
    
            for (int j = 0; j <= i; j++)
            {
    
                //  Judge  j + 1  To  i  Whether the string of is a palindrome string 
                if (isPal(s, j, i - 1))
                    ret[i] = min(ret[i], ret[j] + 1);
            }
        }

        return ret[len];
    }
};

The above method Time complexity of two cycles yes $O(n^2)$ , Determine the time complexity of palindrome string yes $O(n)$ , therefore Total time complexity by $O(n^3)$ .

For long strings , stay OJ When it comes to TLE(Time Limit Exceeded), The method of judging palindrome string can continue to be optimized , The overall time complexity will be $O(n^2)$ .

Judging palindrome string , This is a “ Is it right? ” The problem of , So it can also be realized by dynamic programming

state ：
Substate ： Is the palindrome string from the first character to the second character , The first 1-3, The first 2-5,…

• $F(i,j)$: Character range [i,j] Whether it is palindrome string

State recurrence ：

• $F(i,j)$: true->{ $s[i]==s[j]$ && $F(i+1,j-1)$} OR false
  The above formula indicates that if the first and last characters of the character interval are the same, and after removing the first and last characters of the interval, the character interval is still a palindrome string , Then the original character interval is palindrome string
• From the recurrence formula, we can see that i You need to use the second i + 1 The information in the office , therefore i You should traverse... From the end of the string

initialization ：
$F(i,j)$ = false

Return results ：
matrix $F(n,n)$, Update only half the value （i <= j）,$n^2 / 2 $

class Solution {
    
public:
    vector<vector<bool> > getMat(string& s)
    {
    
        int len = s.size();
        vector<vector<bool> > mat = vector<vector<bool> >(len, vector<bool>(len, false));

        for (int i = len - 1; i >= 0; --i)
        {
    
            //  Judge [i , j] Whether it is palindrome within the scope 
            for (int j = i; j < len; ++j)
            {
    
                if (j == i)
                    mat[i][j] = true;
                else if (j == i + 1)
                    mat[i][j] = (s[i] == s[j]);
                else
                    mat[i][j] = ((s[i] == s[j]) && mat[i + 1][j - 1]);
            }
        }
        return mat;
    }


    int minCut(string s) {
    
        if (s.empty())
            return 0;
        int len = s.size();
        int* ret = new int[len + 1];
        //  Get palindrome string judgment array 
        vector<vector<bool> > mat = getMat(s);
        //  One is long for  i  String , Form palindrome string , At most, it needs to be cut  i - 1 The knife 
        for (int i = 0; i <= len; ++i)
        {
    
            ret[i] = i - 1;
        }

        for (int i = 2; i <= len; ++i)
        {
    
            for (int j = 0; j <= i; ++j)
            {
    
                //  Now judge  j + 1  To  i  Whether the string of is a palindrome string , You can get it directly from the array 
                if (mat[j][i - 1])
                    ret[i] = min(ret[i], ret[j] + 1);
            }
        }

        return ret[len];
    }
};

Sum up , The time complexity of this algorithm is optimized to $O(n^2)$

---

8. Edit distance

---

Original link ： Edit distance

state ：

word1 Before 1,2,3,...m Convert characters to word2 Before 1,2,3,...n Edit distance required for characters

• $F(i,j)$: word1 Before i Characters in word2 Before j Edit distance of characters

State recurrence ：

• $F(i,j)=minF(i-1,j）+1,F(i,j-1)+1,F(i-1,j-1)+(w1[i]==w2[j]?0:1)$

The above formula means to delete , Select a minimum operand in the add and replace operations

• $F(i-1,j)$: $w1[1,...,i-1]$ On $w2[1,...,j]$ Editor's distance , Delete $w1[i]$ The characters of —> $F(i,j)$
• $F(i,j-1)$: $w1[1,...,i]$ On $w2[1,...,j-1]$ Editor's distance , Add a character —> $F(i,j)$
• $F(i-1,j-1)$: $w1[1,...,i-1]$ On $w2[1,...,j-1]$ Editor's distance , If $w1[i]$ And $w2[j]$ identical , Do nothing , Edit distance unchanged , If $w1[i]$ And $w2[j]$ Different , Replace $w1[i]$ The character of is $w2[j]$—> $F(i,j)$

initialization ：
Initialization must be a certain value , If you add an empty string here , To determine the initialization status

• $F(i,0)=i$ :word Edit distance from empty string , Delete operation
• $F(0,i)=i$ : Empty string and word Editor's distance , Increase the operating

Return results ：$F(m,n)$

class Solution {
    
public:
    int minDistance(string word1, string word2) {
    
        if (word1.empty() || word2.empty())
            return max(word1.size(), word2.size());

        int len1 = word1.size();
        int len2 = word2.size();
        vector<vector<int>> ret(len1 + 1, vector<int>(len2 + 1, 0));

        //  initialization 
        // j == 0  when 
        for (int i = 0; i <= len1; ++i)
            ret[i][0] = i;
        // i == 0  when 
        for (int i = 0; i <= len2; ++i)
            ret[0][i] = i;

        for (int i = 1; i <= len1; ++i)
        {
    
            for (int j = 1; j <= len2; ++j)
            {
    
                //  Select Delete first  or  Insert 
                ret[i][j] = min(ret[i - 1][j] + 1, ret[i][j - 1] + 1);
				
                //  Decide whether to replace , If you want to replace , Operands  +1 , On the contrary, it will not change 
                // word1 Of the  i  Characters , The corresponding index is i - 1,word2 Empathy 
                if (word1[i - 1] == word2[j - 1])
                    ret[i][j] = min(ret[i - 1][j - 1], ret[i][j]);
                else
                    ret[i][j] = min(ret[i - 1][j - 1] + 1, ret[i][j]);
            }
        }

        return ret[len1][len2];
    }
};

---

9. Different subsequences

---

Original link ： Different subsequences

state ：
Substate ： from S Before 1,2,...,m A substring of characters and T Before 1,2,...,n The same number of characters

• $F(i,j)$ : S[0 ~ i-1] Substrings in and T[0 ~ j-1] The same number

State recurrence ：
stay $F(i,j)$ We need to consider $S[i-1]=T[j-1]$ and $S[i-1]!=T[j-1]$ Two cases （ here S Of the i The index value of characters is i - 1 , T Empathy ）

• When $S[i-1]=T[j-1]$:
  1. Give Way $S[i-1]$ matching $T[j-1]$, be
     $F(i,j)=F(i-1,j-1)$
  2. Give Way $S[i-1]$ Mismatch $T[j-1]$, Then the problem becomes S[0 ~ i-1] Substrings in and T[0 ~ j-1] The same number , be
     $F(i,j)=F(i-1,j)$
     so ,$S[i-1]=T[j-1]$ when ,$F(i,j)=F(i-1,j-1)+F(i-1,j)$
• When $S[i-1]!=T[j-1]$:
  The problem degenerates into S[0 ~ i-2] Substrings in and T[0 ~ j-1] The same number
  so ,$S[i-1]!=T[j-1]$ when ,$F(i,j)=F(i-1,j)$

initialization ： Introduce an empty string for initialization

• $F(i,0)=1$ —> S The number of substrings is the same as that of empty strings , Only an empty string is the same as an empty string

Return results ：
$F(m,n)$

class Solution {
    
public:
    int numDistinct(string S, string T) {
    
        int lenS = S.size();
        int lenT = T.size();

        vector<vector<int> > ret(lenS + 1, vector<int>(lenT + 1, 0));
        //  initialization 
        for (int i = 0; i <= lenS; ++i)
            ret[i][0] = 1;

        for (int i = 1; i <= lenS; ++i)
        {
    
            for (int j = 1; j <= lenT; ++j)
            {
    
                //  Judge S Of the i Whether the characters are the same as T Of the j The characters are equal 
                //  If equal , You can choose whether to use S Of the i Characters , The final result is   Use S Of the i Characters  +  not used S Of the i Characters 
                //  If it's not equal , Just inherit  S Before i - 1 Characters   And  T Before j Characters   The same number 
                if (S[i - 1] == T[j - 1])
                    ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
                else
                    ret[i][j] = ret[i - 1][j];
            }
        }


        return ret[lenS][lenT];
    }
};

We observed that $ret[i,j]$ The value of is only related to $ret[i-1,j]$ and $ret[i-1,j-1]$ of , So we can use optimization methods similar to knapsack problem , Optimize the space complexity to $O(n)$ .

optimization algorithm ：

class Solution {
    
public:
    int numDistinct(string S, string T) {
    
        int lenS = S.size();
        int lenT = T.size();
        
		//  Just keep the columns 
        vector<int> ret(lenT + 1, 0);

        ret[0] = 1;

        for (int i = 1; i <= lenS; ++i)
        {
    
            //  In order to prevent the value of the previous line from being overwritten before it is used , We must go the other way , From the last column to the first column 
            for (int j = lenT; j >= 1; --j)
            {
    
                if (S[i - 1] == T[j - 1])
                    ret[j] = ret[j] + ret[j - 1];
                else
                    ret[j] = ret[j];
            }
        }

        return ret[lenT];
    }
};

---

summary

---

• Dynamic programming state definition

  • Status source ： Abstract the state from the problem

  • Abstract state ： Each state corresponds to a sub problem

  • There are many definitions of state , But what about verifying the rationality of the state definition ？

    1. Can the solution of a certain state or the solution after multiple states processing correspond to the solution of the final problem .
    2. Recursive relationships can be formed between States .

  • One dimensional state or Two dimensional state ？

    Find clues according to the subject .

    First try the one-dimensional state , When the one-dimensional state is unreasonable , Then define the two-dimensional state .

  • Status of frequently asked questions ：

    • character string ： The state generally corresponds to the substring , A new character is usually added in the state each time .
    • matrix ： Two dimensional state （ When only the data of the previous row is used , It may be optimized into a one-dimensional state ）

Be careful ： In dynamic programming , The most important step is to define the state , If the state definition is unreasonable , There will be a lot of trouble .

---

This is a new series ——【 Writing diary 】, The original intention of Bai chenkai's series is to share some classic questions , So that we can better learn programming .

If there is something wrong with the parsing, please correct it , I'll change it as soon as possible , Thank you for your tolerance .

If you like this series , Please give us more support ！

If this article helps you , Please also give me one The thumb and Little star ️ Give me your support ！ Like Bai Chen 【 Writing diary 】 Series words , Not as good as Focus on Bai Chen , To see the latest updates ！！！

I can't stay up late in the morning , See you in the next article .