解决动态规划问题4步曲

柔光的暖阳◎ 2022-12-31 13:23 119阅读 0赞

## 概述 ##

1.  （确定状态）确定问题状态
    
     *  提炼最后一步
     *  子问题转化
2.  （求得方程）转移方程，把问题方程化
3.  （设初置界）按照实际逻辑设置初始条件和边界情况
4.  （确序再解）确定计算顺序并求解

## 一个案例：最少硬币组合 ##

你打算买一本27元的书，你现有三种硬币，分别面值2元，5元和7元，每种硬币都充足。请问如何用个数最少的硬币组合正好付清？

**正常人第一反应思路**:

最少硬币组合?

*  优先使用大面值硬币 —— 7+7+7+5=26，不符合求解目标27元。
 *  换种组合 —— 7+7+7+2+2+2=27，总共用了6枚硬币正好27元。
 *  实际正确答案 —— 7+5+5+5+5=27，才用了5枚硬币。

所以这里**贪心算法**是并不适用。

题目中关键词“**最少的**”，**这是用到“动态规划”的味道**。

## 解决动态规划问题4步 ##

### 第一步，确定问题状态 ###

动态规划问题求解需要先开一个数组，并确定数组的每个元素f\[i\]代表什么，这就是确定这个问题的状态。这类似于解数学题中，设定x，y，z代表什么。

#### A、确定状态首先提取“最后一步” ####

最优策略必定是K枚硬币`a1, a2, …, aK`面值加起来是27。

**找出不影响最优策略的最后一个独立角色**，这道问题中，那枚最后的硬币`aK`就是最后一步。把`aK`提取出来，硬币`aK`之前的所有硬币面值加总是`27-aK`。因为总体求最硬币数量最少策略，所以拼出`27-aK`的硬币数也一定最少（**重要设定**）。

![在这里插入图片描述][20201229234140887.jpg_pic_center]

#### B、转化子问题 ####

最后一步`aK`提出来之后，我们只要求出“最少用多少枚硬币可以拼出`27- aK`”就可以了。

这种与原问题内核一致，但是规模变小的问题，叫做**子问题**。

为简化定义，我们设**状态`f(X)=最少用多少枚硬币拼出总面值X`**。

我们目前还不知道最后的硬币`aK`面额多少，但它的面额一定只可能是\{2, 5, 7\}之一。

*  如果`aK`是2，`f(27)`应该是`f(27-2) + 1`(加上最后这一枚面值2的硬币）
 *  如果`aK`是5，`f(27)`应该是`f(27-5) + 1`(加上最后这一枚面值5的硬币）
 *  如果`aK`是7，`f(27)`应该是`f(27-7) + 1`(加上最后这一枚面值7的硬币）

除此以外，没有其他的可能了。至此，通过找到原问题最后一步，并将其转化为子问题。

为求面值总额27的最小的硬币组合数的状态就形成了，用以下函数表示：

f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

![在这里插入图片描述][20201229234206163.jpg_pic_center]

### 第二步，转移方程，把问题方程化 ###

f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}

动态规划都是要开数组，所以上面式子改用方括号表示。实际求解动态规划类问题，正确列出转移方程正确基本上就解决一半了。

递归的解法：

// f(X)返回最少用多少枚硬币拼出X
    int f(int X) { 
    	// 0元钱只要0枚硬币
    	if (X == 0) return 0;
    	 // 初始化用无穷大（
    	int res = Integer.MAX_VALUE;
    	 // 最后一枚硬币是2元
    	if (X >= 2) { 
    		res = Math.min(f(X – 2) + 1, res);
    	}
    	// 最后一枚硬币是5元
    	if (X >= 5) { 
    		res =  Math.min(f(X – 5) + 1, res);
    	}
    	// 最后一枚硬币是7元
    	if (X >= 7) {       
    		res =  Math.min(f(X – 7) + 1, res);
    	}
    	return res;
    }

执行图如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]

要算`f(27)`，就要递归`f(25)、f(22)、f(20)`，然后下边依次递归。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 1]

问题明显：**重复递归太多**。

这是求`f(27)`，等待时间还可以接受。如果求`f(100)`呢？

求总体最值，**可优先考虑动态规划**，不要贸然去递归。

### 第三步，按照实际逻辑设置边界情况和初始条件。 ###

如果不按照实际逻辑设置边界情况和初始条件，即使转移方程正确也大概率无法跑通代码。

`f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}`的边界情况是`[x-2]`、`[x-5]`、`[x-7]`不能小于0（硬币面值为正），也不能高于27。

**故对边界情况设定如下**：

**如果硬币面值不能组合出Y，就定义`f[Y]=正无穷`**。例如，`f[-1] = f[-2] = … = 正无穷`，`f[1] = min{f[-1]+1, f[-4]+1,f[-6]+1} = 正无穷`，**特殊情况**：本题的`F[0]`对应的情况为`F[-2]、F[-5]、F[-7]`，按照上文的边界情况设定结果是**正无穷**，但是实际上`F[0]`的结果是存在的（即使用0个硬币的情况下），`F[0]=0`。

可是按照我们刚刚的设定，`F[0]=F[0-2]+1= F[-2]+1=正无穷`。**岂不是矛盾**？这种用转移方程无法计算，但是又实际存在的情况，就必须通过手动定义。这里**手动强制**定义初始条件为：`F[0]=0`。

而从0之后的数值是没矛盾的，比如`F[1]= F[1-2]+1= F[-1]+1=正无穷`（正无穷加任何数结果还是正无穷），`F[2] = F[2-2]+1 = F[0]+1=1`。

### 第四步，确定计算顺序并计算求解 ###

那么开始计算时，是从`F[1]`、`F[2]`开始呢？还是从`F[27]`、`F[26]`开始呢？

判断计算顺序正确与否的原则是：当我们要计算`F[X]`（等式左边，如F\[10\]）的时候，等式右边（`f[X-2]`，`f[X-5]`，`f[X-7]`等）都是已经得到结果的状态，这个计算顺序就是OK的。

**实际就是从小到大的计算方式**（偶有例外的情况）。

例如我们算到`F[12]`的时候，发现`F[11]`、`F[10]`、`F[9]`都已经算过了，这种算法就是对的。而开始算`F[27]`的时候，发现`F[26]`还没有算，这样的顺序就是错的。

很显然这样的情况下写一个for循环就够了。

回到这道题，采用动态规划的算法，每一步只尝试三种硬币，一共进行了27步。算法时间复杂度（即需要进行的步数）为27\*3。

**与递归相比，没有任何重复计算**。

[本文的题目来源：LeetCode - Medium - 322. Coin Change][LeetCode - Medium - 322. Coin Change]

代码如下：

public class CoinChange { 
    	public int coinChange(int[] coins, int amount) { 
    		int[] f = new int[amount + 1];
    		Arrays.fill(f, Integer.MAX_VALUE);
    		f[0] = 0;
    
    		for (int i = 1; i <= amount; i++) { 
    			//如果通过放这个硬币能够达到数量i
    			for(int coin : coins) { 
    				if (i >= coin && f[i - coin] != Integer.MAX_VALUE)
    					// 获得i的数量的硬币数就可能是获得i-A[j]重量硬币数的方案+1
    					// 拿这个方案数量与原本的方案数打擂台，取最小值就行
    					f[i] = Math.min(f[i - coin] + 1, f[i]);
    			}
    		}
    
    		if (f[amount] == Integer.MAX_VALUE) { 
    			return -1;
    		}
    		return f[amount];
    	}
    }

## 总结 ##

1.  这是求最值问题，用动态规划方式求解。（案例：最少硬币组合）
2.  进入求解过程，先确定问题状态
    
     *  提炼最后一步（最优策略中使用的最后一枚硬币`aK`）
     *  子问题转化（最少的硬币拼出更小的面值`X-aK`）
3.  构建转移方程（`f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}`）
4.  设置初始条件和边界情况（`f[0] = 0`, 如果不能拼出Y，`f[Y]=正无穷`）
5.  确定计算顺序并计算求解（`f[0]`, `f[1]`, `f[2]`,…）

[20201229234140887.jpg_pic_center]: /images/20221120/179f7cc42e9146c5ba9c0be42def47c4.png
[20201229234206163.jpg_pic_center]: /images/20221120/1cf49bbe1e25422fae14a30b3bcd8cfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f118d7deed5f4e3d93679960ff9f4b6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/af3eb6247e0f420ea3ce15145ae8cdd8.png
[LeetCode - Medium - 322. Coin Change]: https://leetcode.com/problems/coin-change/