动态规划——简单理解

妖狐艹你老母 2022-05-09 03:16 243阅读 0赞

# 动态规划的基本步骤 #

1.  找出最优解的性质，并刻划其结构特征的。（寻找最优解的子问题结构）
2.  递归的定义最优解。（根据子问题结构建立问题的递归解式求解最优值）
3.  以自底向上的方式计算出最优值（动态规划思想）
4.  根据计算最优值时得到的信息，构造最优解。

--------------------

# 动态规划总体思想 #

--------------------

1.  动态规划算法与分治法类似，其基本思想也是将带求解问题分解成若干子问题
2.  但是经分解得到的子问题往往不是互相独立的。不同问题的数目常常有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

如何减少子问题的重复计算就是动态规划算法的关键解决思想！  
在我们的计算机中，它的最大的优势是什么，就是它的记忆性好，它有无限的存储空间。如果能够保存已解决的子问题的答案，而在需要时再找出以求得的答案，就可以避免大量的重复计算，从而得到多项式时间算法。

--------------------

# 动态规划算法的基本要素 #

--------------------

通过以上，我们可以得到两个动态规划算法的基本要素

## 1. 最优子结构 ##

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

## 2. 重叠子问题 ##

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

# 举个例子 #

**在满足运行效率的要求上，多个矩阵的连乘功能**

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

**在这里我们要知道：对于 p×q 矩阵A 和 q×r 矩阵B，AB需要** **？** **标准乘法计算.**

？= pqr

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

**也就是说不同的加括号的形式，我们矩阵连乘需要的数乘次数是不同的。（这就是我们要讨论的矩阵连乘问题的最优子结构）**

--------------------

# 问题分析 #

## 用递归算法 ##

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

可以看到黄色部分有很多重复的子问题，那可不可以在递归算法中添加表记录已计算的结果？减少计算量？

## 备忘录方法 ##

![在这里插入图片描述][70 5]  
自顶向下  
![在这里插入图片描述][70 6]

## 动态规划 ##

自底向上  
![在这里插入图片描述][70 7]

[70]: /images/20220509/4734105e4eab46f29123de54387c5187.png
[70 1]: /images/20220509/58a6d463c3d44d69b81fd10561a2c508.png
[70 2]: /images/20220509/4bc2c8d6d8ee4500bb1d9c96896700dc.png
[70 3]: /images/20220509/d65344b374c340d78a034c8c4b45b7bf.png
[70 4]: /images/20220509/b28e5744844849cb8e016396ae4db8d5.png
[70 5]: /images/20220509/886bd80e188946efb48403839d12f942.png
[70 6]: /images/20220509/602887c6e5304deb8106bb0b95495a26.png
[70 7]: /images/20220509/9418c369efe74cb2ab296a8980be646d.png