func rob(nums []int) int { n := len(nums) if n == 0 { return0 } if n == 1 { return nums[0] } pre := nums[0] cur := max(nums[0], nums[1]) for i := 2; i < n; i++ { pre, cur = cur, max(cur, pre + nums[i]) } return cur }
func max(x, y int) int { if x > y { return x } return y }
func rob(nums []int) int { n := len(nums) if n == 1 { return nums[0] } dp := make([]int, n) dp[0] = nums[0] dp[1] = nums[0] for i := 2; i < n - 1; i++ { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) } res1 := dp[n - 2] dp[0] = 0 dp[1] = nums[1] for i := 2; i < n; i++ { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) } return max(res1, dp[n-1]) }
func max(x, y int) int { if x > y { return x } return y }
零钱兑换
完全背包问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
func coinChange(coins []int, amount int) int { dp := make([]int, amount + 1) for i := 1; i <= amount; i++ { dp[i] = -1 for _, c := range coins { if i < c || dp[i-c] == -1 { continue } count := dp[i-c] + 1 if dp[i] == -1 || dp[i] > count { dp[i] = count } } } return dp[amount] }
最大子序和
1 2 3 4 5 6 7 8 9 10 11 12 13
func maxSubArray(nums []int) int { res := nums[0] for i := 1; i < len(nums); i++ { if nums[i] + nums[i-1] > nums[i]{ nums[i] += nums[i -1] } if nums[i] > res { res = nums[i] } } return res }
cur := 1 for i := 0; i < len(nums); i++ { cur *= nums[i] res = max(cur, res) if nums[i] == 0 {cur = 1} } cur = 1 for i := len(nums) - 1; i >= 0; i-- { cur *= nums[i] res = max(cur, res) if nums[i] == 0 {cur = 1} } return res }
func max(x, y int) int { if x > y { return x } return y }
func maximalSquare(matrix [][]byte) int { m := len(matrix) n := len(matrix[0]) dp := make([][]int, m) res := 0 // 初始化，并赋值，如果有1，结果为1，特殊处理 for i := 0; i < m; i++ { dp[i] = make([]int, n) for j := 0; j < n; j++ { if matrix[i][j] == '1' { dp[i][j] = 1 res = 1 } } } // 0那一行，最多就是1，不需要进行更新，从1开始遍历 for i := 1; i < m; i++ { for j := 1; j < n; j++ { // 如果当前值是1,则以当前点为右下角包含1的正方形，为其他三个点的最小值+1 // 为0的则 跳过 if dp[i][j] == 1{ dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1 } // 更新res if dp[i][j] > res { res = dp[i][j] } } } return res * res }
// 前缀和加上最大子序和 func maxSumSubmatrix(matrix [][]int, k int) int { rowNum, colNum := len(matrix), len(matrix[0]) // 最小值作为初始结果 result := math.MinInt32 // 按列遍历，起始指针 for left := 0; left < colNum; left ++ { rowSum := make([]int, rowNum) // 按列遍历，结束指针 for right := left; right < colNum; right++ { // 按行遍历，逐列想加，每一列都是之前列的行行和 for row := 0; row < rowNum; row++ { rowSum[row] += matrix[row][right] } // 找最大值，每一列的最大子序和，就是矩形区域的和 result = max(result, maxSubArrBelowK(rowSum, k)) if result == k { return k } } } return result }
// 找最大子序和，因为有k限制 func maxSubArrBelowK(arr []int, k int) int { // 先按动态规划找最大子序和，找到可以减少时间复杂度 sum, max, l := arr[0], arr[0], len(arr) for i := 1; i < l; i++ { if sum > 0 { sum += arr[i] } else { sum = arr[i] } if sum > max { max = sum } } // 如果结果小于k，则找到，返回 if max <= k { return max } // 结果大于k，则只能暴力法去找，最接近k的 max = math.MinInt32 for left := 0; left < l; left++ { sum := 0 for right := left; right < l; right++ { sum += arr[right] if sum > max && sum <= k { max = sum } if max == k { return k } } } return max }
// 最长 有效括号，双向遍历法 func longestValidParentheses(s string) int { if s == "" { return0 } left, right, res := 0, 0, 0 for i := 0; i < len(s); i++ { // 左右计数++ if s[i] == '(' { left++ } if s[i] == ')' { right++ } // 右括号比左括号多，则重置，前面的舍弃 if right > left { left = 0 right = 0 } // 更新结果 if left == right { res = max(res, right) } } // 以上会漏掉一种就是左括号始终比右括号多，这种是找不到的 // 逆向遍历，正向排除右比左多的，逆向排除左比右多的 left, right = 0, 0 for i := len(s) - 1; i >= 0; i-- { if s[i] == '(' { left++ } if s[i] == ')' { right++ } if right < left { left = 0 right = 0 } if left == right { res = max(res, right) } } return2 * res }
func max(x, y int) int { if x > y { return x } return y }
// 动态规划方法 func longestValidParentheses(s string) int { if s == "" || len(s) < 2 { return0 } dp := make([]int, len(s)) res := 0 // 从1开始遍历 for i := 1; i < len(s); i++ { // 结尾是）才能形成有效括号，只看结尾是）的前面， （的dp值都是0 if s[i] == ')' { // 找前面的（，如果前一个就是（，前一个dp值是0，也能找到 pre := i - 1- dp[i - 1] // 如果大于0，且找到是（，则结果+2 if pre >= 0 && s[pre] == '(' { dp[i] = dp[i-1] + 2 // 如果有再前一个，则加上再前一个的dp值 if pre - 1 >= 0 { dp[i] += dp[pre - 1] } } // 返回最大值 res = max(res, dp[i]) } } return res }
func max(x, y int) int { if x > y { return x } return y }
func findLength(A []int, B []int) int { m := len(A) n := len(B) dp := make([][]int, m + 1) for i := 0; i < m + 1; i++ { dp[i] = make([]int, n + 1) } res := 0 for i := m - 1; i >= 0; i-- { for j := n - 1; j >= 0; j-- { if A[i] == B[j] { dp[i][j] = dp[i + 1][j + 1] + 1 } else { dp[i][j] = 0 } if res < dp[i][j] { res = dp[i][j] } } } return res }
滑动窗口解法 func findLength(A []int, B []int) int { res := 0 m := len(A) n := len(B) // 一个不动，一个动 for i := 0; i < m; i++ { win := min(n, m - i) res = max(res, handle(A, B, i, 0, win)) } for i := 0; i < n; i++ { win := min(m, n - i) res = max(res, handle(A, B, 0, i, win)) } return res }
func handle(A, B []int, sA, sB, win int) int { res := 0 tmp := 0 for i := 0; i < win; i++ { if A[sA + i] == B[sB + i] { tmp++ } else { tmp = 0 } res = max(res, tmp) } return res }
func min(x, y int) int { if x > y { return y } return x }
func max(x, y int) int { if x > y { return x } return y }