Leetcode dynamic programming

q5 Longest text substring

Subject portal

Answer key

First, find out the dynamic transfer equation , You can find dp[i][j] If it's a palindrome string , that dp[i + 1][j - 1] Must be palindrome string , among dp[i][j] Indicates a string subscript i To j The string of . At the same time, boundary conditions should also be considered , That is, if the length of the substring is less than 2, Then it must be a palindrome string , If the substring length is equal to 2, Then the palindrome string only needs to meet dp[i] == d[j].

func longestPalindrome(s string) string {
    
	n := len(s)
	dp := make([][]bool, n)
	for i, _ := range dp {
    
		dp[i] = make([]bool, n)
	}
	ans := ""
	//  The first layer traverses the length of the substring 
	for l := 0; l < n; l++ {
    
		//  The second layer is the left boundary of the substring 
		for i := 0; i + l < n; i++ {
    
			// j Is the right boundary of the substring 
			j := i + l
			if l == 0 {
    
				dp[i][j] = true
			} else if l == 1 {
    
				dp[i][j] = (s[i] == s[j])
			} else {
    
				dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1])
			}
			//  Update Max 
			if dp[i][j] && l + 1 > len(ans) {
    
				ans = s[i:j + 1]
			}
		}
	}
	return ans
}

q53 Maximum subarray and

Subject portal

Answer key

Traversal array , Open up a new array dp, Loop traversal nums, Give Way dp[i] = nums[i], And then determine dp[i] + dp[i - 1] Is it greater than dp[i], If greater than, let dp[i] += dp[i - 1]

func maxSubArray(nums []int) int {
    
	dp := make([]int, len(nums))
	dp[0] =  nums[0]
	maxSum := nums[0]
	for i := 1; i < len(nums); i++ {
    
		dp[i] = nums[i]
		if dp[i - 1] + dp[i] > dp[i] {
    
			dp[i] += dp[i - 1]
		}
		if dp[i] > maxSum {
    
			maxSum = dp[i]
		}
	}
	return maxSum
}

q62 Different paths

Subject portal

Answer key

The dynamic transfer equation of this topic is very simple , Because you can only go down and right , therefore dp[i][j] = dp[i - 1][j] + dp[i][j - 1], Finally, deal with the boundary conditions ,dp[i][0] and dp[0][j] All equal to 1, Because there is only one path to the border .

func uniquePaths(m int, n int) int {
    
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
    
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for j := 0; j < n; j++ {
    
		dp[0][j] = 1
	}
	for i := 1; i < m; i++ {
    
		for j := 1; j < n; j++ {
    
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		}
	}
	return dp[m - 1][n - 1]
}

q64 Minimum path sum

Subject portal

Answer key

This problem is solved by dynamic programming , The dynamic transfer equation is dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]), Then deal with the boundary situation , Boundary is when i == 0 perhaps j == 0 When , This is the time dp[i][0] = dp[i - 1][0],dp[0][j] = dp[0][j - 1].

func minPathSum(grid [][]int) int {
    
	m, n := len(grid), len(grid[0])
	dp := make([][]int, m)
	dp[0] = make([]int, n)
	dp[0][0] = grid[0][0]
	for i := 1; i < m; i++ {
    
		dp[i] = make([]int, n)
		dp[i][0] = grid[i][0]
		dp[i][0] += dp[i - 1][0]
	}
	for j := 1; j < n; j++ {
    
		dp[0][j] = grid[0][j]
		dp[0][j] += dp[0][j - 1]
	}
	for i := 1; i < m; i++ {
    
		for j := 1; j < n; j++ {
    
			dp[i][j] = grid[i][j]
			dp[i][j] += min(dp[i - 1][j], dp[i][j - 1])
		}
	}
	return dp[m - 1][n - 1]
}
func min(a, b int) int {
    
	if a < b {
    
		return a
	} else {
    
		return b
	}
}

q70 climb stairs

Subject portal

Answer key

This problem can be solved by recursion , The recurrence formula is step[i] = step[i - 1] + step[i - 2], Then deal with the boundary conditions , When i == 1 when ,step[1] = 1, When i == 2 when ,step[2] = 2.

func climbStairs(n int) int {
    
	if n <= 2 {
    
		return n
	}
	step1, step2, step3 := 1, 2, 0
	for i := 3; i <= n; i++ {
    
		step3 = step1 + step2
		step1 = step2
		step2 = step3
	}
	return step3
}

q118 Yang hui triangle

Subject portal

Answer key

This problem is solved by dynamic programming , The state transition equation is dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j], Then deal with the boundary conditions , If the number of rows is less than 3, Then all elements are 1, When the number of lines is greater than or equal to 3 when , The state transition equation is satisfied only when the number of columns is not the first and last , Otherwise, it's all for 1 .

func generate(numRows int) [][]int {
    
	res := [][]int{
    {
    1}}
	if numRows == 1 {
    
		return res
	}
	res = append(res, []int{
    1, 1})
	if numRows == 2 {
    
		return res
	}
	for i := 3; i <= numRows; i++ {
    
		var rows []int
		for j := 1; j <= i; j++ {
    
			if j != 1 && j != i {
    
				rows = append(rows, res[i - 2][j - 2] + res[i - 2][j - 1])
			} else {
    
				rows = append(rows, 1)
			}
		}
		res = append(res, rows)
	}
	return res
}

q300 Longest ascending subsequence

Subject portal

Answer key

First define an array dp Used to save the length of the longest ascending subsequence up to the current element position . Use a two-layer loop , The first level of loop traversal nums Array , The second layer of loop traversal starts from zero to nums The previous element of the current element of the array , If the current element satisfies nums[i] > num[j] && dp[j] + 1 > dp[i], Is executed dp[i] = dp[j] + 1 To update the longest ascending subsequence .

func lengthOfLIS(nums []int) int {
    
	dp := make([]int, len(nums))
	maxLen := 0
	for i := 0; i < len(nums); i++ {
    
		dp[i] = 1
		for j := 0; j < i; j++ {
    
			if nums[i] > nums[j] && dp[j] + 1 > dp[i] {
    
				dp[i] = dp[j] + 1
			}
		}
		if dp[i] > maxLen {
    
			maxLen = dp[i]
		}
	}
	return maxLen
}

q1143 Longest common subsequence

Subject portal

Answer key

Define an array dp[i][j] Express text1[1…i] and text2[1…j] The length of the longest common subsequence of , So the final answer is dp[len1][len2].
This problem can be divided into three cases ：

1. text1[i] Not in the common subsequence , that dp[i][j] = dp[i - 1][j]
2. text2[j] Not in the common subsequence , that dp[i][j] = dp[i][j - 1]
3. text1[i] == text2[j], This is the time dp[i][j] = dp[i - 1][j - 1] + 1

dp[i][j] Take the maximum of the above three cases . Then deal with the boundary conditions ,dp[i][0] and dp[0][j] All for 0 .

func longestCommonSubsequence(text1 string, text2 string) int {
    
	len1, len2 := len(text1), len(text2)
	dp := make([][]int, len1 + 1)
	for i := 0; i <= len1; i++ {
    
		dp[i] = make([]int, len2 + 1)
	}
	for i := 1; i <= len1; i++ {
    
		for j := 1; j <= len2; j++ {
    
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
			if text1[i - 1] == text2[j - 1] {
    
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
			}
		}
	}
	return dp[len1][len2]
}

func max(a, b int) int {
    
	if a > b {
    
		return a
	} else {
    
		return b
	}
}