The core thought of DP is that, if a question can be divided into sub-questions, and each sub-questions can use the answer of last one, then, to solve the final question, we just need to get the answer of the most rent sub-question.
For example, if I want to measure the distance between A and B. And if there’s a milestone in C, saying that the distance from B and C is 100 km, them I just need to measure the distance from A and C, and simply plus the result with 100. When we using DP, there will be lots of “C”.
In algorithm questions, the key feature is that if we can make question divided, and this usually happens in 2D-array, for instance, like 2D graph question or comparing two strings.
Given two strings
text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.
Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.
1 <= text1.length <= 1000
1 <= text2.length <= 1000
In such scenario, we usually set an 2D matrix as the ‘milestone’, and usually name it as
the key is : dp(i,j) means the longest common subsequence of text1[:i] and text2[:j]. If text1[i]==text2[j], then dp(i,j) should equal dp(i-1,j-1)+1 Otherwise, dp(i,j)=max(dp(i-1,j), dp(i,j-1))
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: n=len(text1) m=len(text2) dp=[*(m+1) for i in range(n+1)] for i in range(n): for j in range(m): if text1[i]==text2[j]: #create generator dp[i+1][j+1]=dp[i][j]+1 else: dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]) print(dp) return dp[-1][-1]
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: for i in range(len(matrix)): for j in range(len(matrix)): matrix[i][j]=int(matrix[i][j]) if matrix[i][j] and i and j: matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1])+1 return len(matrix) and max(map(max,matrix)) **2
If we overwatch the change of dp matrix, we will find interesting result.