第9周 高级动态规划、字符串算法
2021-11-20
5分钟阅读时长
题目数量：35+
第19课 | 高级动态规划
1. 动态规划、状态转移方程串讲
参考链接
func climbStairs(n int) int {
p, q := 1, 1
for i := 2; i <= n; i++ {
p, q = q, p + q
}
return q
}
// 方法一： 标准二维dp
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
dp[i][0] = 1
}
for i := 0; i < n; i++ {
dp[0][i] = 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]
}
// 方法二：高级一维dp
func uniquePaths(m int, n int) int {
dp := make([]int, n)
for i := range dp {
dp[i] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] += dp[j-1]
}
}
return dp[n-1]
}
// 方法一：标准二维dp
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
if obstacleGrid[0][0] == 1 {
return 0
}
m, n := len(obstacleGrid), len(obstacleGrid[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
dp[0][0] = 1
for i := 1; i < m; i++ {
if obstacleGrid[i][0] != 1 {
dp[i][0] = dp[i-1][0]
}
}
for j := 1; j < n; j++ {
if obstacleGrid[0][j] != 1 {
dp[0][j] = dp[0][j-1]
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] != 1 {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1]
}
// 方法二：高级一维dp
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m, n := len(obstacleGrid), len(obstacleGrid[0])
dp := make([]int, n)
if obstacleGrid[0][0] == 0 {
dp[0] = 1
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if obstacleGrid[i][j] == 1 {
dp[j] = 0
//} else if j > 0 && obstacleGrid[i][j-1] == 0 {
} else if j > 0 {
dp[j] += dp[j-1]
}
}
}
return dp[n-1]
}
// 方法一：标准dp写法
func rob(nums []int) int {
n := len(nums)
if n < 2 {
return nums[0]
}
dp := make([]int, n)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < n; i++ {
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 方法二：空间优化dp
func rob(nums []int) int {
pre, cur := 0, 0
for _, num := range nums {
pre, cur = cur, max(cur, pre + num)
}
return cur
}
// 方法一：标准dp
func minPathSum(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
dp[0][0] = grid[0][0]
// 初始化 第一列
for i := 1; i < m; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
// 初始化 第一行
for j := 1; j < n; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
return dp[m-1][n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// 方法二：空间优化dp
func minPathSum(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([]int, n)
dp[0] = grid[0][0]
for i := 1; i < n; i++ {
dp[i] = dp[i-1] + grid[0][i]
}
for i := 1; i < m; i++ {
// 第一列
dp[0] += + grid[i][0]
for j := 1; j < n; j++ {
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
}
}
return dp[n-1]
}
func maxProfit(prices []int) int {
n := len(prices)
dp0, dp1 := 0, -prices[0]
for i := 1; i < n; i++ {
// 不持有股票
dp0 = max(dp0, dp1 + prices[i])
// 持有股票
dp1 = max(dp1, -prices[i])
// 以上两句可优化为如下
// dp0, dp1 = max(dp0, dp1 + prices[i]), max(- prices[i], dp1)
}
return dp0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
课后作业
在第 9 周学习总结中，写出63. 不同路径 II 这道题目的状态转移方程。
2. 高级动态规划题目详解
参考链接
func climbStairs(n int) int {
p, q := 1, 1
for i := 2; i <= n; i++ {
p, q = q, p + q
}
return q
}
// 状态转移方程：dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])
func minCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n + 1)
for i := 2; i <= n; i++ {
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// 空间优化
func minCostClimbingStairs(cost []int) int {
n := len(cost)
p, q := 0, 0
for i := 2; i <= n; i++ {
p, q = q, min(p+cost[i-2], q+cost[i-1])
}
return q
}
课后作业
第20课 | 字符串算法
1. 字符串基础知识和引申题目
参考链接
字符串基础问题
字符串操作问题
异位词问题
回文串问题
2. 高级字符串算法
最长子串、子序列问题
字符串 +DP 问题
3. 字符串匹配算法
参考链接
课后作业
本周作业
通知
- 因五一假期期间（5 月 4 号）已解锁第 9 周课程，下周无新视频课程解锁。请同学们自觉完成第 8、9 周作业，按时提交：第 8 周作业截止 5 月 10 号 23:59；第 9 周作业截止 5 月 17 号 23:59。
- 第 9周作业： https://u.geekbang.org/lesson/11?article=226915
- 5 月 17 号 0 点解锁期末考试周，请同学们完成期末串讲视频课程，并自行安排复习。
- 同时，当周会安排覃超老师进行期末答疑直播（具体时间以微信班级群通知为准）请同学们将问题填写至下方链接： https://jinshuju.net/f/vEOJCH
简单
中等
在第 9周学习总结中，写出不同路径 2 这道题目的状态转移方程。