浅入动态规划

作者: 牛子威_8期强化班 | 来源:发表于2022-03-19 15:40 被阅读0次

众所周知在算法中，存在着一群元老级别难度的算法，比如：动态规划，dfs，贪心，分治等，近段时间在我长时间的研究下，重要对此有了一点点了解，现在和大家分享一下

首先，在我看来，动态规划就是将一个题，分解为无数个子问题，并且这些子问题的算法，解题过程都是一样的子问题。然后通过每个子问题找到对应的递推公式，最后得出最终的正确答案。

第二，我们需要搞清楚边界条件，比如说什么时候开始，什么时候停止，这是一个重要的环节，当边界调节设置错误时，这道题将全军覆没。

接下来，就是要确定实现方法：在我看来我一般习惯使用双层for循环。

来举个简单的例子：蓝桥杯算法训练的拿金币问题，我们到最下面那个格子，我们要拿到最多的金币，因为最后一个格子的金币是固定的，所以我们只需要知道走到上一个位置所能拿到的最多的金币即可，接着推，我们只需要找到走到这一个格子上一步能取到的最大值即可

最后不论我们怎么走，最后总会退到原点，现在就是思路的转换，从倒推到正着打代码。

接下来，我们创建一个数组，记录走到每一个格子可能拿到的最大值即可。这道题的边界条件很简单，就是数组的0号位存储第一个格子的金币即可。

网友评论

本文标题：浅入动态规划

本文链接：https://www.haomeiwen.com/subject/qhxadrtx.html

浅入动态规划