矩阵连乘暨动态规划

发表于 更新于 分类于 Waline：

推荐观看b站上的up主九章算术发布的视频，有关于动态规划，个人认为讲的非常好，老师还是一名清华大学毕业生！

前言：现在懂了一点…

先来看一道题目：用2、5、7拼成27，假设2、5、7各有很多，要求所需要的个数最少。

1
2
graph LR
A[2?] --> B[5?] --> C[7?] --> D[27]

这是一道比较常见的可以用动态规划求解的题目，用4步来解决此题

1.确定状态

最后一步

子问题

本题最后一步就是不管怎样进行取舍，最后拿的一定是2、5、7三个中的一个，不可能是其它，因此就可以分条件了，原文题就转化为如何用最少数量拼凑出27-2、27-5、27-7，这样问题规模就缩小了，就划分成了三个子问题，即三个中哪个所需最少，同样可以继续对27-2、27-5、27-7进行类似分析，思路就逐步明朗了，由此可以联想到用递归算法进行求解，但是用递归会有重复步骤，效率不高，这里使用动态规划算法

2.转移方程

经过上述分析，大致有了一个思路，接下来就要列转移方程了，这里用函数f[x]来表示拼出x所需的最少数量，本题我们计算f[27]

1
2


未完待续！