状态转移方程⌗

无后效性⌗

如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。

一旦 \(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 讨论：

  1. 先写出穷举的方法
  2. 找出不必要的重复计算
  3. 写出 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\)

  • 若优先使用 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\)）

将上述过程反过来就可以一步步推出结果。

实现⌗ 

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]\)

LeetCode 真题⌗

See also⌗