动态规划#
本文主要讲了动态规划四要素,并且用一个数字三角形为例,介绍了两种动态规划抽象思考过程,如何根据输入的二维数组,抽象出矩阵坐标,介绍两种完全相反的实现方式——自底向上、自顶向下。
实现四要素#
?>更详细解释参考下面面两幅图笔记
DP状态
- 用$f[i]$ 或者$f[i][j]$代表某些特定条件下规模更小问题的答案
- 规模更小的问题,用参数i,j之类的来划定
?> 1. f[i]
是什么?
2. f[i][j]
是什么?答:例子1:dp[i][j]
点(i,j)
走到最底层叶节点的最短路径
3. 矩阵是如何抽象出来的?举几个具体的题目,描述一下抽象成矩阵的过程。
4. 状态这一要素有什么用途?答:个人猜测是,方便描述某一层的状态
DP方程
- 大问题拆解为对小问题的依赖
- $f[i][j]=$ 通过规模更小的一些状态,对这些状态求$max、min、sum、or$来进行推导
?> 1. 常见的大问题有哪些? 答:最短路径
2. 常见大问题拆成小问题的例子?
3. 常见推导DP方程的过程,文字描述出来。
DP初始化
- 设定无法再拆解的极限小的状态下的值
- 这些值无法用方程、通项公式来表示
- 如$f[i][0]$或者$f[0][i]$
DP答案
- 最后的答案是什么,答案的最后一步是什么
- 如$f[i][j]$或者$f[0][0]、min(f[n][1],f[n][2]…)$
接下来我们以动态规划四要素为例,学习一下数字三角形动态规划的解法。
数字三角形#
回忆一下数字三角形的矩阵抽象过程
自底向上-数字三角形#
时间复杂度:$O(n^2)$
空间复杂度:$O(n^2)$
?> 1. 自底向上是指什么?
2. 如何理解贪心追求的是当前利益。答:我的理解是贪心只关注当前这一步的最佳值(最大、最小)
3. 如何理解DP追求的是长远利益。答:我的理解是DP关注的是所有走法的最佳值(最大、最小)
4. 贪心算法常见的题目是什么?贪心算法的定义是什么?
递归四要素为:
状态:f[i][j]
代表从(i,j)
点走到最底层的最短路径
动态方程: f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];
初始化:底部那一层的叶节点,i = n - 2
起始点:底部那一层的叶节点
终点:(0,0)
1 | public class Solution { |
自顶向下-数字三角形#
时间复杂度:$O(n^2)$
空间复杂度:$O(n^2)$
?> 自顶向下是指什么?
答:是指两个方向,一是点可能来自于的方向,皆来自于顶部;二是指遍历的方向,遍历的方向是从根节点向下至底部的叶节点。
四要素分别为:
状态是dp[i][j]
,dp[i][j]
是指从(0,0)
点走到(i,j)
点的最短路径
答案是min(dp[n-1])
,dp[n-1]
是最底一层的叶节点,min(dp[n-1])
是指最底一层叶节点的最小值,即dp[n][i]
使dp[n]
最小的值
动态方程 dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
初始化是两条边dp[i][0]
、dp[i][i]
,因为这聊天边没有左上角的店和正上方的点
起始点是(0,0)
1 | public class Solution { |
参考#
九章算法2020
【labuladong】动态规划核心套路详解
动态规划解题套路框架
【动态规划专题班】ACM总冠军、清华+斯坦福大神带你入门动态规划算法