leetcode_动态规划合集

面试题47. 礼物的最大价值

题目

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 13521 可以拿到最多价值的礼物

提示:

0 < grid.length <= 200 0 < grid[0].length <= 200

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

显而易见的DP问题,求最值,依然是三步走

  • 确定状态

    • 对于每一步的结果 dp[i][j] = A[i][j]+ 左边格子结果dp[i][j-1]或上面格子结果dp[i-1][j]
    • 要求最大, 即求 max{dp[i][j-1], dp[i-1][j]}
  • 转移方程

    $dp[i][j] = max{dp[i-1][j], dp[i][j-1]} + A[i][j]$

  • 起始和边界值

    • 起始值:dp[0][0] = A[0][0]
    • 边界值来自
      • 第一列:只能来自同列上一行
      • 第一行:只能来自同行上一列

问题分析清楚了就可以代码实现了

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%的用户

面试题 08.02. 迷路的机器人

题目

设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格(有障碍物)。设计一种算法,寻找机器人从左上角移动到右下角的路径。

网格中的障碍物和空位置分别用 1 和 0 来表示。

返回一条可行的路径,路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]

解释: 输入中标粗的位置即为输出表示的路径,即 0行0列(左上角) -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列(右下角) 说明:r 和 c 的值均不超过 100。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/robot-in-a-grid-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

dp[i][j]表示到达A[i][j]最多路径数

A[i][j] 不是障碍时:

  • 转移方程为:

    dp[i][j] = max{dp[i-1][j], dp[i][j-1]} + 增加的步数

    • 增加的步数:dp[i-1][j], dp[i][j-1]二者取最大值
      • 如果二者都不为0,那么路径数要+1
      • 否则直接取不为零的那条路径
  • 如果是路障,dp[i][j]直接取0

找到最终路径后,倒过来遍历,把路径存入结果后输出

详细的过程看代码:

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%的用户

322. 零钱兑换

题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明: 你可以认为每种硬币的数量是无限的。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/coin-change 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

经典的DP题,三步走:

  1. 确定状态:

    • 最后一步 dp[i]:金额为i时,需要的金币数
    • 子问题:最少的金币数拼出的余额 amount-dp[i]
  2. 转移方程 dp[i] = min{dp[i-c[0]]+1, dp[i-c[1]]+1, ..., dp[i-c[n-1]]+1}(假设c为金币)

  3. 初始值和边界

    • F[0]=0,如果拼不出,dp[i]设置为初始值
    • 边界:i-c[j]>=0
  4. 计算顺序:dp[i] = min{dp[amount-c1]+1,dp[amount-c2]+1,dp[amount-c3]+1},左边依赖右边,所以从小到大计算

解答

// 金额为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%的用户

300. 最长上升子序列

题目

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]它的长度是 4

说明:

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-increasing-subsequence 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

dp[i] = max{dp[i], dp[j]+1} (dp[j] 为 0~i-1中的最大)

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
}

329. 矩阵中的最长递增路径

题目

给定一个整数矩阵,找出最长递增路径的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。

示例 1:

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]

示例 2:

输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]注意不允许在对角线方向上移动

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

dp + dfs 在DFS的过程中进行dp记录

// 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
}

买股票

121. 买卖股票的最佳时机

题目

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 股票价格 = 1的时候买入在第 5 股票价格 = 6的时候卖出最大利润 = 6-1 = 5 
 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

暴力

对每个数进行分析,求最大

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%的用户
优化—DP
  1. 记录【今天之前:买入的最小值】
  2. 计算【今天之前最小值买入,今天卖出的获利】,也即【今天卖出的最大获利】
  3. 比较【每天的:最大获利】,取最大值即可
//      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%的用户

122. 买卖股票的最佳时机 II

题目

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 股票价格 = 1的时候买入在第 3 股票价格 = 5的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 
     随后在第 4 股票价格 = 3的时候买入在第 5 股票价格 = 6的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 股票价格 = 1的时候买入在第 5  股票价格 = 5的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 
     注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出
     因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

贪心

只要今天比昨天的高,就抛出。少量多次

其实按照题目的要求,并不允许这样操作。

  • 比如 [1, 2, 3]
    • 正常流程:1买 3卖 = 2
    • 贪心:1卖 2卖 + 2买 3卖 = 2
  • 结果是一样的,但是题目要求不允许同时参与多笔交易
  • 其实贪心的原理就是 把所有增量累加起来
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%的用户
动态规划

每一天有两种状态,要么买入了,要么未买入。且两种状态都依赖于昨天的情况

dp[i]表示第i天两种情况分别对应的最大收入

  • 当天持有:这一支要么是按兵不动的,要么是把今天买的
  • 当天未持有:要么是按兵不动,要么是把今天的卖掉了
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%的用户

279. 完全平方数

题目

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/perfect-squares 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

// 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
}

343. 整数拆分

343

题目

Difficulty: 中等

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

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

示例 2:

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

说明: 你可以假设 _n _不小于 2 且不大于 58。

Solution

Language: Go

// 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
}

72. 编辑距离

题目

72. 编辑距离

Difficulty: 困难

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

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

示例 2:

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

Solution

题解看这位大佬的,图文并茂:经典动态规划:编辑距离 Language: Go

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
}

1143. 最长公共子序列

题目

1143. 最长公共子序列 Difficulty: 中等

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 _子序列 _是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • 输入的字符串只含有小写英文字符。

Solution

题解见注释

Language: Go

//      ""  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
}

打家劫舍系列

思路见:团灭打家劫舍问题

198. 打家劫舍

题目

198. 打家劫舍 Difficulty: 简单

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你**在不触动警报装置的情况下,**能够偷窃到的最高金额。

示例 1:

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

示例 2:

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

Solution

Language: Go

// 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
}

213. 打家劫舍 II

题目

213. 打家劫舍 II

Difficulty: 中等

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都**围成一圈,**这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你**在不触动警报装置的情况下,**能够偷窃到的最高金额。

示例 1:

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

示例 2:

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

Solution

第一个和最后一个不能同时抢。 所以:要么不抢第一个,要么不抢最后一个。 注意,不抢第一个的时候,最后一个可抢可不抢;另一种情况同理 取两种情况中的最大值

Language: Go

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
}

337. 打家劫舍 III

题目

337. 打家劫舍 III

Difficulty: 中等

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

示例 1:

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

     3
    / \
   2   3
    \   \ 
     3   1

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

示例 2:

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

     3
    / \
   4   5
  / \   \ 
 1   3   1

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

Solution

Language: Go

/**
 * 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
}

LCP 19. 秋叶收藏集

题目

LCP 19. 秋叶收藏集

小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 r y, 其中字符r表示一片红叶,字符 y 表示一片黄叶。 出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

示例 1:

输入leaves = "rrryyyrryyyrr"
输出2
解释调整两次将中间的两片红叶替换成黄叶得到 "rrryyyyyyyyrr"

示例 2:

输入leaves = "ryr"
输出0
解释已符合要求不需要额外操作

提示:

  • 3 <= leaves.length <= 10^5

  • leaves 中只包含字符 'r' 和字符 'y'

解答

DP三步走,确定初始状态、转移方程、边界值

这里是一个二维DP,二维不使用二维数组,而是使用一个结构体表示二维上的三种状态。

每一片叶子都可能存在三种地方:头部[..axx..]、中部[..xax..]、尾部[..xxa..],每变色一次,操作就要+1。 因此就出现了选择问题,产生较小的值。比如:ryyy 第二片 可以作为 后三片的首部[变色] 或 前三片的中部[不变]

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% 的用户

分享: