Dynamic programming
When it comes to dynamic planning, many people are more headache, because this kind of thing is really not as a person, it is really difficult to even want to write out, any is stuck in a certain step, can not extricate themselves for a long time. I, too, have suffered from dynamic programming, and I have suffered from it so badly that I don’t even want to think about it. Without further ado, let’s get to know it.
concept
What is dynamic programming? The basic idea of dynamic programming is to decompose the problem to be solved into several sub-problems, and obtain the solution of the original problem by using the solutions of these sub-problems. Usually dynamic programming problems are accompanied by this dynamic array DP to record the answers to all the subproblems. You compute a subproblem, you fill it into a DP array, and dp arrays can be defined as one-dimensional arrays, two-dimensional arrays, or even three-dimensional arrays depending on the complexity of the problem, depending on the problem, sometimes one-dimensional arrays can be solved, but DP might be more easily defined as two-dimensional arrays. And there’s always a relationship between the elements of this DP array, which we call the state transition equation,
Dynamic programming is often used to solve problems with optimal properties and no after-effects, such as the longest palindrome and the familiar knapsack problem. Then it is necessary to explain what is called no aftereffect: once the state of a certain stage is determined, the subsequent process is no longer affected by the previous states and decisions, and the changes after this stage are only related to this stage, and have nothing to do with the stages experienced before this stage. In other words, each subproblem is a new problem, and when studying the next subproblem, it is only related to the current subproblem, and has nothing to do with the subproblem before it
The problem solving thought is tetralogy
1. Make suredpIs the state of: defined as one dimensional two dimensional or three dimensional? What does it mean?
2. Determine the state transition equation
3. Initialization, i.edpThe value of an element that can be retrieved from an array
4. Calculate from the bottom updpAnd obtain the optimal value
sample
Given a string s, find the longest sequence of subroutines and return the length of the sequence.
A subsequence is defined as a sequence in which some characters or none of the characters are deleted without changing the order of the remaining characters
The basic idea
Before we do that, we need to look at what a sequence of texts is, and we need to distinguish it from a sequence of texts, which has to be continuous, and a sequence of texts is a sequence that is composed without changing the alphabetical order. For example,bab, the anagram substring BA, AB,bab, but there is a subsequence bb, so the two are different.
So let’s do the tetralogy
State of dp array
First, we need to consider how to define the dp array. In this problem, we assume that we define the one-dimensional array dp[], so what does it mean? And this is a substring, so how do we represent the notion of a substring? So obviously, it’s not a good idea to define a one-dimensional array here. So let’s define dp array as a two-dimensional array, dp[I][j] means the maximum length of the subsequence from I to j.
Equation of state
And then we need to think about equations of state, which is always the hard part. We need to grasp the essence. When recording a certain state, we only need to know how dp[I][J] defines the state, without knowing how it is derived.
In general, when we think about it, we don’t talk about special cases, we talk about general cases
In palindromes, the most important logic is s[I]=s[j]. If I is adjacent to j, then we can define the maximum length of dp[I][j] in the subroutine sequence from I to j as 2. So we can keep going, what if we have more letters? In other words, when I and j are not adjacent, we need to determine the maximum length of the subsequence in judging dp[I + 1][j-1]. In this case, dp[I][j] = dp[I + 1][j-1] + 2.
Since it is a subroutine sequence, we also need to consider that S [I] is not the same as s[j]. At this time, it means that the addition of s[I] and S [j] at the same time cannot increase the maximum length of the subroutine string in the interval [I,j] +2. At this time, s[I] and S [j] should be added separately to see which subsequence can form the longest subroutine sequence.
If s[j] is added, then the maximum length of dp[I +1][j] needs to be considered for the original dp[I +1][j].
If s[I] is added, then the maximum length of dp[I][J-1] should be considered for the original dp[I][J-1].
The dp [I] [j] must take both the maximum value, namely: dp [I] [j] = Max (dp [j], [I + 1] dp [I] [1]).
Initialize the
When I is the same as j, it is obvious that dp[I][j] = 1, that is, if I is equal to j, set it to 1
From the bottom up
Obviously, the order of computation here is I needs to start at 0, and j needs to start at the last bit of s. Because our dp[I][j] needs to be obtained by dp[I][j-1], the final maximum value is dp[0][size-1].
Specific code
class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0)); for (int i = 0; i < s.size(); i++) dp[i][i] = 1; For (int I = s.size() -1; int I = s.size() -1; i >= 0; i--) { for (int j = i + 1; j < s.size(); j++) { if (s[i] == s[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][s.size() - 1]; }};Copy the codeconclusion
Dynamic planning, the road is very long, this is just the tip of the iceberg, I just swim in the ocean of code, nearly drowned, yourself is to strengthen practice in the future, need to constantly improve themselves, but in the dynamic programming, tetralogy was very effective, at least not so funny, remember a proverb: practice more, learn more, review more, think more!
I hope I can help you, thank you!