动态规划

2019-05-02 本文已影响0人 topshi

动态规划题目特点

1. 计数

有多少种方式走到右下角
有多少种方法选出k个数使得和是sum

2.求最大最小值

从左上角走到右下角路径的最大数字和
最长上升子序列长度

3.求存在性

取石子游戏，先手是否必胜
能不能选出k个数使得和是sum

动态规划四个组成部分：

确定状态
- 研究最优策略的最后一步
- 化为子问题
转移方程
- 根据子问题定义直接得到
初始条件和边界情况
计算顺序
- 利用之前的计算结果

最值型动态规划

Coin Change
假设你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合正好付清，不需要对方找钱。

动态规划组成部分一：确定状态

状态是动态规划的核心
解动态规划时需要定义一个数组，数组的每一个元素f[i]或者f[j][j]代表什么
确定状态需要两个意识：
- 最后一步
- 子问题

最后一步
1-不知道最优策略，但最优策略肯定是K枚硬币 $a_1,a_2,...,a_k$ 面值加起来是27
2-所以肯定有一枚最后的硬币： $a_k$
关键点1：不关心前面k-1枚硬币如何拼出 $27-a_k$ ，甚至不知道 $a_k和K$ ，但是确定了前面的硬币拼出了 $27-a_k$
关键点2：因为是最优策略，所以拼出 $27-a_k$ 的硬币数一定要最少，否则矛盾。
子问题
1 - 需要求出最少用多少枚硬币可以拼出 $27-a_k$
2 - 原问题是最少用多少枚硬币拼出27
3 - 原问题转化成了一个规模更小的子问题： $27-a_k$
4 - 设状态 $f(X) = 最少用多少枚硬币拼出X$
最后一枚硬币只可能是2，5或7
若 $a_k == 2$ ， $f(27)$ 应该是 $f(27 - 2) + 1$ (加上最后的一枚硬币2)
若 $a_k == 5$ ， $f(27)$ 应该是 $f(27 - 5) + 1$ (加上最后的一枚硬币5)
若 $a_k == 7$ ， $f(27)$ 应该是 $f(27 - 7) + 1$ (加上最后的一枚硬币7)
要求最少的硬币数：
$f(27) = min{f(27 - 2), f(27 - 5), f(27 - 7)} + 1$

动态规划组成部分二：转移方程

设状态 $f(X) =$ 最少用多少枚硬币拼出 $X$
对于任意 $X$ ， $f(27) = min{f(27 - 2), f(27 - 5), f(27 - 7)} + 1$

动态规划组成部分三：初始条件和边界情况

$X < 0$ 时， $f(X) = +\infty$
初始条件： $f(0) = 0$

动态规划组成部分三：计算顺序

初始条件： $f(0) = 0$
然后计算 $f(1),f(2),...,f(27)$
大多数情况都是从小到大地算，这样当算 $f(x)$ 时，前面的 $f(x-2),f(x-5)和f(x-7)$ 都已经算过了。

求最值型动态规划小结

1.确定状态
- 最后一步（最优策略中使用的最后一枚硬币 $a_k$ ）
- 化成子问题（最少的硬币拼出更小的面值 $27-a_k$
2.转移方程
- $f(X) = min{f(X - 2), f(X - 5), f(X - 7)} + 1$
3.初始条件和边界情况
- $f(0) = 0$ ，如果不能拼出 $X$ ， $f(X) = +\infty$
4.计算顺序
- $f(0),f(1),...$

计数型动态规划

Unique Paths

给定m行n列的网格，有一个机器人从左上角(0, 0)出发，每一步可以向下或者向右走一步，问有多少种不同的方式走到右下角

动态规划组成部分一：确定状态

最后一步：机器人走到右下角之前的最后一步：向右或者向下
右下角坐标为(m - 1, n - 1)，那么前一步机器人一定是在(m - 2, n - 1)或者(m - 1, n - 2)
子问题 ——从左上角走到(m - 2, n - 1)和从左上角走到(m - 1, n - 2)；假设从左上角走到(m - 2, n - 1)有 $X$ 种方式，从左上角走到(m - 1, n - 2)有 $Y$ 种方式，那么走到(m - 1, n - 1)就有 $X+Y$ 种方式。
问题转化为机器人有多少种方式从左上角走到(m - 2, n - 1)和(m - 1, n - 2)
状态：设 $f[i][j]$ 为机器人有多少种方式从左上角走到 $(i,j)$