众所周知在算法中,存在着一群元老级别难度的算法,比如:动态规划,dfs,贪心,分治等,近段时间在我长时间的研究下,重要对此有了一点点了解,现在和大家分享一下
首先,在我看来,动态规划就是将一个题,分解为无数个子问题,并且这些子问题的算法,解题过程都是一样的子问题。然后通过每个子问题找到对应的递推公式,最后得出最终的正确答案。
第二,我们需要搞清楚边界条件,比如说什么时候开始,什么时候停止,这是一个重要的环节,当边界调节设置错误时,这道题将全军覆没。
接下来,就是要确定实现方法:在我看来我一般习惯使用双层for循环。
来举个简单的例子:蓝桥杯算法训练的拿金币问题,我们到最下面那个格子,我们要拿到最多的金币,因为最后一个格子的金币是固定的,所以我们只需要知道走到上一个位置所能拿到的最多的金币即可,接着推,我们只需要找到走到这一个格子上一步能取到的最大值即可
最后不论我们怎么走,最后总会退到原点,现在就是思路的转换,从倒推到正着打代码。
接下来,我们创建一个数组,记录走到每一个格子可能拿到的最大值即可。这道题的边界条件很简单,就是数组的0号位存储第一个格子的金币即可。