日韩黄色网上,99久久精,久久国产亚洲精品

動態(tài)規(guī)劃題目特點

1. 計數(shù)

有多少種方式走到右下角
有多少種方法選出k個數(shù)使得和是sum

2.求最大最小值

從左上角走到右下角路徑的最大數(shù)字和
最長上升子序列長度

3.求存在性

取石子游戲，先手是否必勝
能不能選出k個數(shù)使得和是sum

動態(tài)規(guī)劃四個組成部分：

確定狀態(tài)
- 研究最優(yōu)策略的最后一步
- 化為子問題
轉(zhuǎn)移方程
- 根據(jù)子問題定義直接得到
初始條件和邊界情況
計算順序
- 利用之前的計算結(jié)果

最值型動態(tài)規(guī)劃

Coin Change
假設你有三種硬幣，分別面值2元，5元和7元，每種硬幣都有足夠多，買一本書需要27元，如何用最少的硬幣組合正好付清，不需要對方找錢。

動態(tài)規(guī)劃組成部分一：確定狀態(tài)

狀態(tài)是動態(tài)規(guī)劃的核心
解動態(tài)規(guī)劃時需要定義一個數(shù)組，數(shù)組的每一個元素f[i]或者f[j][j]代表什么
確定狀態(tài)需要兩個意識：
- 最后一步
- 子問題

最后一步
1-不知道最優(yōu)策略，但最優(yōu)策略肯定是K枚硬幣 $a_1,a_2,...,a_k$ 面值加起來是27
2-所以肯定有一枚最后的硬幣： $a_k$
??關鍵點1：不關心前面k-1枚硬幣如何拼出 $27-a_k$ ，甚至不知道 $a_k和K$ ，但是確定了前面的硬幣拼出了 $27-a_k$
??關鍵點2：因為是最優(yōu)策略，所以拼出 $27-a_k$ 的硬幣數(shù)一定要最少，否則矛盾。
子問題
1 - 需要求出最少用多少枚硬幣可以拼出 $27-a_k$
2 - 原問題是最少用多少枚硬幣拼出27
3 - 原問題轉(zhuǎn)化成了一個規(guī)模更小的子問題： $27-a_k$
4 - 設狀態(tài) $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)
要求最少的硬幣數(shù)：
$f(27) = min{f(27 - 2), f(27 - 5), f(27 - 7)} + 1$

動態(tài)規(guī)劃組成部分二：轉(zhuǎn)移方程

設狀態(tài) $f(X) =$ 最少用多少枚硬幣拼出 $X$
對于任意 $X$ ， $f(27) = min{f(27 - 2), f(27 - 5), f(27 - 7)} + 1$

動態(tài)規(guī)劃組成部分三：初始條件和邊界情況

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

動態(tài)規(guī)劃組成部分三：計算順序

初始條件： $f(0) = 0$
然后計算 $f(1),f(2),...,f(27)$
大多數(shù)情況都是從小到大地算，這樣當算 $f(x)$ 時，前面的 $f(x-2),f(x-5)和f(x-7)$ 都已經(jīng)算過了。

求最值型動態(tài)規(guī)劃小結(jié)

1.確定狀態(tài)
- 最后一步（最優(yōu)策略中使用的最后一枚硬幣 $a_k$ ）
- 化成子問題（最少的硬幣拼出更小的面值 $27-a_k$
2.轉(zhuǎn)移方程
- $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),...$

計數(shù)型動態(tài)規(guī)劃

Unique Paths

給定m行n列的網(wǎng)格，有一個機器人從左上角(0, 0)出發(fā)，每一步可以向下或者向右走一步，問有多少種不同的方式走到右下角

動態(tài)規(guī)劃組成部分一：確定狀態(tài)

最后一步：機器人走到右下角之前的最后一步：向右或者向下
右下角坐標為(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$ 種方式。
問題轉(zhuǎn)化為機器人有多少種方式從左上角走到(m - 2, n - 1)和(m - 1, n - 2)
狀態(tài)：設 $f[i][j]$ 為機器人有多少種方式從左上角走到 $(i,j)$