Python|Dynamic Programming Classic Case
Principles of Dynamic Programming##
The dynamic programming algorithm divides the problem to be solved into a series of overlapping sub-problems, defines the solution strategy of each sub-problem through the recurrence relationship, and records the solution of the sub-problem at any time, and finally obtains the solution of the original problem, avoiding overlapping Repeated solution of sub-problems.
Essentials of Dynamic Planning##
There are three elements in the dynamic programming algorithm, namely the optimal substructure, boundary and state transition function.
Optimal substructure: the optimal state of each stage can be directly obtained from one or some states of a previous stage;
Boundary: the solution of the smallest subset of the problem;
State transition function: the specific mode of transition from one stage to another, describing the relationship between two adjacent sub-problems.
The longest ascending subsequence problem##
Given an unordered integer array, find the length of the longest ascending subsequence.
1. Example
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest ascending subsequence is [2,3,7,101], and its length is 4.
2. Problem-solving ideas:
Status definition:
Create a list dp with the same length as the input list nums. The value of dp[i] represents the length of the longest subsequence of the first i digits of nums.
3. Optimal substructure:
When calculating dp[i], we need to traverse the list interval of [0,i) to make a judgment (j∈[0,i)):
(1) When nums[i]>nums[j], this is an ascending subsequence, so dp[i]=dp[j]+1
(2) When nums[i]>nums[j], this is not the ascending subsequence skip
4. Transfer equation: dp[i]=max(dp[i],dp[j]+1)
5. Initial state: Each element can at least become a subsequence individually, and the initial value of all elements in all dp lists is 1
| class Solution: def lengthOfLIS(self, nums) : len_nums=len(nums) dp=[1 for i in range(len_nums)] for i in range(1,len_nums): for j in range(i): if nums[i]>nums[j]: dp[i]=max(dp[i],dp[j]+1) return max(dp) |
to sum up####
The above is all the content of this article. If you just started to learn dynamic programming, don't worry if you don't understand it. The dynamic programming code is traceable, and you need to practice more similar topics. For everyone, there are other solutions to this question. I hope readers can communicate more and post your code in the message area for your reference.
END
Chief Editor | Wang Nanlan
Responsible Editor | KeeCTh
**The stronger the ability, the greater the responsibility. Seek truth from facts, rigorous and meticulous. **
** ——Where2go team**