第6周 动态规划
2021-11-20
3分钟阅读时长
题目数量：25+
第12课 动态规划
1.动态规划的实现与关键点
参考连接
# go 代码模板
func recursion(level int, param1, param2, ...) {
# recursion terminator
if level > MAX_LEVEL {
process_result
return
}
# process logic in current level
process(level, data...)
# drill down
recursion(level + 1, p1, ...)
# reverse the current level status if needed
}
func divide_conquer(problem, param1, param2, ...) {
# recursion terminator
if problem == nil {
print_result
return
}
# prepare data
data = prepare_data(problem)
subproblems = split_problem(problem, data)
# conquer subproblems
subresult1 = divide_conquer(subproblems[0], p1, ...)
subresult2 = divide_conquer(subproblems[1], p1, ...)
subresult3 = divide_conquer(subproblems[2], p1, ...)
# process and generate the final result
result = process_result(subresult1, subresult2, subresult3, …)
# revert the current level states
}
2.DP例题解析：Fibonacci数列、路径计算
3.DP例题解析：最长公共子序列
参考连接
func uniquePaths(m int, n int) int {
// 二维dp 0->n
// 精简一维dp 0->n
}
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
// 二维dp 0->n
// 精简一维dp 0->n
}
func longestCommonSubsequence(text1 string, text2 string) int {
}
4.实战题目解析：三角形最小路径和
实战题目
func climbStairs(n int) int {
}
func minimumTotal(triangle [][]int) int {
}
5.实战题目解析：最大子序列和
实战题目
func maxSubArray(nums []int) int {
}
func maxProduct(nums []int) int {
}
func coinChange(coins []int, amount int) int {
}
6.实战题目解析：打家劫舍
实战题目
// 只能交易1次
func maxProfit(prices []int) int {
}
// 交易无数次
func maxProfit(prices []int) int {
}
// 只能交易2次
func maxProfit(prices []int) int {
}
// k次交易
func maxProfit(k int, prices []int) int {
}
// 不限交易次数，含冷冻期
func maxProfit(prices []int) int {
}
// 不限交易次数，含有手续费
func maxProfit(prices []int, fee int) int {
}
高级 DP 实战题目
func numSquares(n int) int {
}
- 72. 编辑距离 （重点）
func minDistance(word1 string, word2 string) int {
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func canJump(nums []int) bool {
}
func jump(nums []int) int {
}
func uniquePaths(m int, n int) int {
}
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
}
func uniquePathsIII(grid [][]int) int {
}
func coinChange(coins []int, amount int) int {
}
func change(amount int, coins []int) int {
}
注意：请大家先消化前面的实战题目，高级 DP 的方法和题解会在课程后面解锁。
本课学习问题反馈
你在本课的学习和练习遇到了哪些问题，欢迎在这里留下你的疑问，我们会收集大家的共性问题提交给助教和老师，帮助大家在班级社群分享和下次直播答疑中解决这些问题。
本周作业及下周预习
本周作业
中等
func minPathSum(grid [][]int) int {
}
func numDecodings(s string) int {
}
func maximalSquare(matrix [][]byte) int {
}
- 621. 任务调度器 重点
func leastInterval(tasks []byte, n int) int {
}
func countSubstrings(s string) int {
}
困难
func minDistance(word1 string, word2 string) int {
}
下周预习
预习知识点
- 红黑树（上）：为什么工程中都用红黑树这种二叉树？
- 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树
- 搜索：如何用 A* 搜索算法实现游戏中的寻路功能？
- Trie 树：如何实现搜索引擎的搜索关键词提示功能？
- B+ 树：MySQL 数据库索引是如何实现的？
- 搜索：如何用 A* 搜索算法实现游戏中的寻路功能？
- 索引：如何在海量数据中快速查找某个数据？