- tags: Algorithm
状态转移方程
无后效性
如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。
一旦 \(f(n)\) 确定，“我们如何凑出 \(f(n)\) ”就再也用不着了：
- 要求出 \(f(15)\)，只需要知道 \(f(14)\),\(f(10)\),\(f(4)\) 的值，
- 而 \(f(14)\),\(f(10)\),\(f(4)\) 是如何算出来的，对之后的问题没有影响。
“未来与过去无关”，这就是无后效性。
最优子结构
大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”：
\(f(n)\) 的定义需要蕴含“最优”，利用 \(f(14)\),\(f(10)\),\(f(4)\) 的最优解，我们即可算出 \(f(15)\) 的最优解。
能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
DP 思路
参见 LeetCode 讨论：
- 先写出穷举的方法
- 找出不必要的重复计算
- 写出 DP
练习
0x00 硬币找零
描述
假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。
状态转移公式
公式 \(f(n)=min\{f(n-1),f(n-3),f(n-5)\} + 1\)
检查是否满足上面提到的两个特性：
- 无后效性：对于 \(n\)，一旦 \(f(n)\) 确定，以后只关心 \(f(n)\) 的值，不关心怎么计算的；
- 最优子结构：对于 \(n\)，只要 \(n - 1\) \(n - 3\) \(n - 5\) 能是最优解，那么就能计算出 n;
推导过程
假设找零 15：
-
若优先使用 5 元硬币 \(cost = f(10) + 1 = 2 + 1 = 3\)
-
使用 5 元： \(f(10)=f(5) + 1\)
- \(f(5)=1\)
-
使用 3 元： \(f(10)=f(7) + 1\)
- \(f(7)=f(4) + 1 = 2 + 1 = 3\)
- \(f(4)= 1 + 1\)
- \(f(7)=f(4) + 1 = 2 + 1 = 3\)
-
-
若优先使用 3 元硬币 \(cost = f(12) + 1 = 4 + 1 = 5\)
- \(f(12)=f(7) + 1\) – 上面已经算出 \(f(7)=3\)
-
若优先使用 1 元硬币 \(cost = f(14) + 1\)
- \(f(14)=f(13)+1\)
- \(f(13)=f(12) + 1 = 4 + 5\) (上面已经算出 \(f(12)=4\)）
- \(f(14)=f(13)+1\)
将上述过程反过来就可以一步步推出结果。
实现
package dp
// 假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。
func getCoinNumber(total int) int {
f := make([]int, total + 1, total + 1)
for i := 1; i <= total; i++ {
if i - 5 >= 0 {
f[i] = f[i - 5] + 1
} else if i - 3 >= 0 {
f[i] = f[i - 3] + 1
} else if i - 1 >= 0 {
f[i] = f[i - 1] + 1
}
}
return f[total]
}
上面算法实现有一个问题，就是每次计算时只优先考虑采用最大面值（类似贪心算法），无法应对某些情况，对比下面代码
package dp
import "math"
func min(x, y int) int {
if x < y {
return x
}
return y
}
// 假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。
func getCoinNumber(total int) int {
f := make([]int, total + 1, total + 1)
for i := 1; i <= total; i++ {
cost := math.MaxInt32
if i - 1 >= 0 {
cost = min(cost, f[i - 1] + 1)
}
if i - 3 >= 0 {
cost = min(cost, f[i - 3] + 1)
}
if i - 5 >= 0 {
cost = min(cost, f[i - 5] + 1)
}
if cost == math.MaxInt32 {
panic("error")
}
f[i] = cost
}
return f[total]
}
0x01单路取苹果
描述
一个矩形区域被划分为 \(N*M\) 个小矩形格子，在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，最后到达(N,M)，每经过一个格子就把其中的苹果全部拿走。请找出能拿到最多苹果数的路线。
思路
这题是 0x00 的扩展，格子 A[N][M] 的苹果数量为 \(max\{A[N-1][M],A[N][M-1]\}+A[N][M]\)