leetcode_动态规划合集

func maxValue(grid [][]int) int {
    if grid == nil || len(grid)==0 || len(grid[0])==0 {
        return 0
    }
    
    // Golang里面初始化一个二维dp还是很难受的
    m, n := len(grid)-1, len(grid[0])-1
    // dp长度和宽度和原数组保持一致，所以下面要+1
    dp := make([][]int, m+1)
    for k, _ := range dp {
        dp[k] = make([]int, n+1)
    }
    
    // 起始值
    dp[0][0] = grid[0][0]
    // 边界值
    for k, _ := range grid {
        if k > 0 {
            dp[k][0] = dp[k-1][0] + grid[k][0]
        }
    }
    for k, _ := range grid[0] {
        if k > 0 {
            dp[0][k] = dp[0][k-1] + grid[0][k]
        }
    }
    
    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
        }
    } 
    return dp[m][n]
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

// 执行用时 :8 ms, 在所有 Go 提交中击败了95.29%的用户
// 内存消耗 :4.4 MB, 在所有 Go 提交中击败了100.00%的用户

func pathWithObstacles(obstacleGrid [][]int) [][]int {
	if obstacleGrid == nil || len(obstacleGrid) == 0 || len(obstacleGrid[0]) == 0 {
		return [][]int{}
	}

	// 初始化二维dp
	m, n := len(obstacleGrid)-1, len(obstacleGrid[0])-1
	dp := make([][]int, m+1)
	for k := range dp {
		dp[k] = make([]int, n+1)
	}

	var ret [][]int
	// 出发点和终点有障碍
	if obstacleGrid[0][0] == 1 || obstacleGrid[m][n] == 1 {
		return ret
	}

	// 初始值和边界值
	dp[0][0] = 1 // 初始的时候有一种路径
	for i := 1; i <= n; i++ {
		// 障碍
		if obstacleGrid[0][i] == 1 {
			dp[0][i] = 0
		} else {
			dp[0][i] = dp[0][i-1]
		}
	}
	for i := 1; i <= m; i++ {
		// 障碍
		if obstacleGrid[i][0] == 1 {
			dp[i][0] = 0
		} else {
			dp[i][0] = dp[i-1][0]
		}
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if obstacleGrid[i][j] == 1 {
				// 此路不通
				dp[i][j] = 0
			} else {
				// 不需要求和 本题只用求是否有路径
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	// 没有找到路径
	if dp[m][n] == 0 {
		return ret
	}

	// 倒推求路径
	for m != 0 || n != 0 {
		ret = append(ret, []int{m, n})
		var up, left int
		// 往上走的路径数
		if m > 0 {
			up = dp[m-1][n]
		}

		// 往左走的路径数
		if n > 0 {
			left = dp[m][n-1]
		}

		if up >= left {
			m--
		} else {
			n--
		}
	}
	ret = append(ret, []int{0, 0})
	return reverse(ret)
}

func reverse(arr [][]int) [][]int {
	l := len(arr) - 1
	for i := 0; i <= l; i++ {
		arr[i], arr[l] = arr[l], arr[i]
		l--
	}
	return arr
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
// 执行用时 :8 ms, 在所有 Go 提交中击败了85.00%的用户
// 内存消耗 :4.4 MB, 在所有 Go 提交中击败了100.00%的用户

// 金额为i时需要最少的硬币：
func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }

    min := func(x, y int) int {
        if x > y {
            return y
        }
        return x
    }

    // 创建DP(1～27种情况)
    dp := make([]int, amount+1)
    // 从1到27开始搜索
    for i := 1; i <= amount; i++ {
        // 假设金额为i时需要无穷多个金币（后面找到最优的时候替换）
        dp[i] = math.MaxInt32

        // 尝试每种金币，找最优
        // dp[i] = min{dp[i-c[0]]+1, dp[i-c[1]]+1, ..., dp[i-c[n-1]]+1}
        for _, c := range coins {
            // 处理边界值
            if i >= c && dp[i-c] != math.MaxInt32 {
                // 找最优
                dp[i] = min(dp[i-c]+1, dp[i])
            }
        }
    }

    // 金额数为amount所需dp[amount]，为最大值
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

// 执行用时 :12 ms, 在所有 Go 提交中击败了75.86%的用户
// 内存消耗 :6 MB, 在所有 Go 提交中击败了65.00%的用户

func lengthOfLIS(nums []int) int {
    l := len(nums)
    if l <= 1 {
        return l
    }

    dp := make([]int, l)
    for k := range dp {
        dp[k] = 1
    }
    for i := 1; i < l; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    var m int
    for _, v := range dp {
        if v > m {
            m = v
        }
    }
    return m
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

// if  dp[i][j] = max{dfs[上下左右]} + 1
func longestIncreasingPath(matrix [][]int) int {
    if len(matrix) == 0 {
        return 0
    }
    // 初始化DP
    m, n, res := len(matrix), len(matrix[0]), 1
    dp := make([][]int, m)
    for k, _ := range dp {
        dp[k] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            res = max(res, dfs(matrix, dp, i, j))
        }
    }
    return res
}

// dfs 直到求出DP
func dfs(matrix, dp [][]int, i, j int) int {
    if dp[i][j] != 0 {
        return dp[i][j]
    }

    left, top, right, bot := 1, 1, 1, 1

    if j-1>=0 && matrix[i][j-1] > matrix[i][j] {
        left += dfs(matrix, dp, i, j-1)
    }
    if i-1>=0 && matrix[i-1][j] > matrix[i][j] {
        top += dfs(matrix, dp, i-1, j)
    }
    if j+1<len(matrix[0]) && matrix[i][j+1] > matrix[i][j] {
        right += dfs(matrix, dp, i, j+1)
    }
    if i+1<len(matrix) && matrix[i+1][j] > matrix[i][j] {
        bot += dfs(matrix, dp, i+1, j)
    }
    ret := max(left, max(right, max(top, bot)))
    dp[i][j] = ret
    return ret
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func maxProfit(prices []int) int {
    if len(prices) < 2 {
        return 0
    }

    max := math.MinInt32
    for k, v := range prices {
        for i := 0; i < k; i++ {
            if v - prices[i] > max {
                max = v - prices[i]
            }
        }
    }
    if max < 0 {
        return 0
    }
    return max
}
// 执行用时 :324 ms, 在所有 Go 提交中击败了6.41%的用户
// 内存消耗 :3.1 MB, 在所有 Go 提交中击败了61.95%的用户

//      7, 1, 5, 3, 6, 4
// dp:  0, 7, 1, 
func maxProfit(prices []int) int {
    if len(prices) < 2 {
        return 0
    }

    // 记录每天之前 最低价格
    dp := make([]int, len(prices))
    var max int
    for i := 1; i < len(prices); i++ {
        var now int
        if i == 1 {
            dp[1] = prices[0]
            now = prices[1] - prices[0]
        } else {
            dp[i] = min(dp[i-1], prices[i-1])
            now = prices[i] - dp[i]
        }

        if now > 0 && now > max {
            max = now
        }
    }
    return max
}

func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}
// 执行用时 :4 ms, 在所有 Go 提交中击败了96.98%的用户
// 内存消耗 :3.3 MB, 在所有 Go 提交中击败了6.19%的用户

func maxProfit(prices []int) int {
    if prices == nil && len(prices) < 2 {
        return 0
    }

    var sum int
    for k, v := range prices {
        if k == 0 {
            continue
        }

        if v > prices[k-1] {
            sum += v-prices[k-1]
        }
    }
    return sum
}
// 执行用时 :4 ms, 在所有 Go 提交中击败了95.42%的用户
// 内存消耗 :3.1 MB, 在所有 Go 提交中击败了52.63%的用户

type sta struct {
    unHold int // 当天不持有股票（作为后面的抄底）时， 最大利润
    hold   int // 当天持有股票时，最大利润
}

func maxProfit(prices []int) int {
    if prices == nil || len(prices) < 2 {
        return 0
    }
    l := len(prices)
    dp := make([]sta, l)
    dp[0] = sta{
        unHold: 0,
        hold:   -prices[0],
    }
    for i := 1; i < l; i++ {
        // 如果今天没买入：这一支要么是按兵不动的，要么是把今天买的
        dp[i].unHold = max(dp[i-1].unHold, dp[i-1].hold + prices[i])
        // 如果今天持有：要么是按兵不动，要么是把今天的卖掉了
        dp[i].hold = max(dp[i-1].hold, dp[i-1].unHold - prices[i])
    }
    return dp[l-1].unHold
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
// 执行用时 :4 ms, 在所有 Go 提交中击败了95.42%的用户
// 内存消耗 :3.6 MB, 在所有 Go 提交中击败了6.58%的用户

// dp[i]代表和等于n时，所需要最少的完全平方数
// dp[i] = min(dp[i-j*j]+1, dp[i]) n-i*i>=0&&i>=1
// 这里的+1就是加上这个i*i平方数。n-i*i=0就是这个数就是个完全平方数（4）
func numSquares(n int) int {
    dp := make([]int, n+1)
    // 初始化
    for k := range dp {
        dp[k] = math.MaxInt32 
    }
    // 边界值
    dp[0], dp[1] = 0, 1
    
    for i := 2; i <= n; i++ {
        // j*j 是小于 i 的所有 “完全平方数”
        for j := 1; j*j <= i; j++ {
            // dp[12] = min{dp[12-1]+1, dp[12-4]+1, dp[12-9]+1}
            	// dp[11] = min{dp[11-1]+1, dp[11-4]+1, dp[11-9]+1}
            		// ...
            	// dp[8] = min{dp[8-4]+1, dp[8-1]+1}
            		// ...
            	// dp[3] = min{dp[3-1]+1}
            dp[i] = min(dp[i], dp[i-j*j]+1)
        }
    }
    return dp[n]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

// dp[10] = 3 x 3 x 4
// 
// dp[10] = max{
//      dp[10-1]*dp[1], 
//      dp[10-2]*dp[2], 
//      dp[10-3]*dp[3],
//          dp[7] = max{dp[6]*dp[1], dp[5]*dp[2], dp[4]*dp[3]}
//      dp[10-4]*dp[4], 
//      dp[10-5]*dp[5]
//  }
// dp[i] = max{dp[i], dp[i-j]*d[j]} j = 1~i
func integerBreak(n int) int {
    if n <= 3 {
        return n-1
    }
    
    dp := make([]int, n+1)
    // 3得最优拆分应该是1*2=2
    // 但是当填表时，若后面更大的数i拆分的时候用到了3的dp值，就不应该返回其最优拆分2
    // 而是返回3本身，只有这样才能让idp[i]最大
    dp[1], dp[2], dp[3] = 1, 2, 3
    for i := 4; i <= n; i++ {
        for j := 1; j <= i/2; j++ {
            dp[i] = max(dp[i-j]*dp[j], dp[i])
        }
    }
    return dp[n]
}
​
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    
    dp := make([][]int, m+1)
    for k := range dp {
        dp[k] = make([]int, n+1)
    }
    
    for i := 1; i <= m; i++ {
        dp[i][0] = i
    }
    for i := 1; i <= n; i++ {
        dp[0][i] = i
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                // 增删改操作“前”的最小DP + 一步操作
                // r -> ap
                // 删：r -> ra -> rap -> ap
                // 增：r -> a   -> ap
                // 改：r -> rp  -> ap
                //      ""  a   ap
                //  ""  0   1   2   不变  增   增
                //  r   1   1   2   ↓删  ↘改   
                //  ra  2   1   2   增   跳过  a增p(→)、rap删r↓、rp改r↘
                dp[i][j] = minThree(
                    dp[i-1][j],// 删
                    dp[i][j-1], // 增
                    dp[i-1][j-1], // 改
                ) + 1
            }
        }
    }
    return dp[m][n]
}
​
func minThree(x, y, z int) int {
    return minInt32(x, minInt32(y, z))
}
​
func minInt32(x, y int) int {
    if x > y {
        return y
    }
    return x
}

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

//      ""  a   b   c   d   e
//  ""  0   0   0   0   0   0
//  a   0   1   1   1   1   1
//  c   0   1   1   2   2   2
//  e   0   1   1   2   2   3
//  比较左后一个字母，相等就+1，否则取max{上，左}
//  if s1[i] == s2[j] {
//      dp[i][j] = dp[i-1][j-1] + 1    
//  } else {
//      dp[i][j] = max{dp[i-1][j], dp[i][j-1]}
//  }
func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for k := range dp {
        dp[k] = make([]int, n+1)
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}
​
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

// dp[i] = max{dp[i-1], dp[i-2]+a[i]}
// 二维
func rob(nums []int) int {
    if nums == nil || len(nums) < 1 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    
    dp := make([]int, len(nums))
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])
    
    for i := 2; i < len(nums); i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    }
    return dp[len(nums)-1]
}
​
// 一维
func rob(nums []int) int {
	if nums == nil || len(nums) < 1 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	dp_i_1, dp_i_2 := nums[0], max(nums[0], nums[1])
	dp_i := 0
	for i := 2; i < len(nums); i++ {
		dp_i = max(dp_i_2, dp_i_1+nums[i])
		dp_i_1 = dp_i_2
		dp_i_2 = dp_i
	}
	return dp_i
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

func rob(nums []int) int {
    if len(nums) < 1 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    
    return max(robRange(nums, 0, len(nums)-2), robRange(nums, 1, len(nums)-1))
}

func robRange(nums []int, low, high int) int {
    dpi1, dpi2, dpi := 0, 0, 0
    for i := low; i <= high; i++ {
        dpi = max(dpi1+nums[i], dpi2)
        dpi1 = dpi2
        dpi2 = dpi
    }
    return dpi
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    ret := dp(root)
    return max(ret[0], ret[1])
}

// 返回的数组：[]int{不抢的收益，抢的收益}
func dp(root *TreeNode) []int {
    if root == nil {
        return []int{0, 0}
    }
    
    left, right := dp(root.Left), dp(root.Right)
    // 抢这一家（加上不抢的收益）
    rob := root.Val + left[0] + right[0]
    
    // 不抢这一家，下家可抢可不抢，取决于收益大小
    unRob := max(left[0], left[1]) + max(right[0], right[1])
    return []int{unRob, rob}
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

type Node struct{
    Head int
    Body int
    Foot int
}

const (
    COLOR_YELLOW = 'y'
    COLOR_RED = 'r'
    INF = math.MaxInt32
)

func minimumOperations(lfs string) int {
    var (
        l = len(lfs)
        dp = make([]Node, l)
    )
	
    // 初始化
    dp[0] = Node { // 第一片不可能出现在中部和尾部
        Head: checkColor(lfs[0], COLOR_YELLOW), // 若出现在头部，且为黄色，操作+1
        Body: INF,
        Foot: INF,
    }
    dp[1] = Node { // 第二片不可能出现在尾部（题目给出至少三片）
        Foot: INF,
    }
	
    // dp 流程，从第二个开始
    for i := 1; i < l; i++ {
        var (
            pre = dp[i-1] // 上一个DP
            isR = checkColor(lfs[i], COLOR_RED) // 若为红色，操作+1
            isY = checkColor(lfs[i], COLOR_YELLOW) // 若为黄色，操作+1
        )
		
        // 选优过程：当前节点 当作 相邻三个节点的首部或中部或尾部 来变色
        // 比如 ryyy  第二片 可以作为 后三片的首部[变色] 或 前三片的中部[不变]
        dp[i].Head = isY + pre.Head // 当前节点 当作 首部节点 来操作，为黄色就+1
        dp[i].Body = isR + min(pre.Head, pre.Body) // 当前节点 当作 中间节点 来操作，若为红色就+1，再加上上个 DP 操作较少的情况

        if i >= 2 {
            // 当前节点 当作 尾部节点 来操作，若为黄色就+1，再加上前一个节点操作较少的情况
            dp[i].Foot = isY + min(pre.Body, pre.Foot)
        }
    }
    return dp[l-1].Foot
}

func checkColor(a, b byte) int {
    if a == b {
        return 1
    }
    return 0
}

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

// 用时：12 ms, 在所有 Go 提交中击败了 97.83% 的用户
// 内存消耗：9 MB, 在所有 Go 提交中击败了 43.48% 的用户