华为二面出的这个题,非常经典的动态规划题目....
还是刷题太少了,不然的话应该是能刷到的
针对这道题有一些感悟
1、回溯+记忆化搜索=动态规划(这句话仍然是适用的)
回溯本质上是一种暴力解法
可以通过以下两种方式进行时间复杂度优化
(1)减去不必要的枝干
(2)记忆化搜索
我们通过减枝可以去除不必要的搜索
记忆化搜索可以去除重复的搜索
2、本身我需要的是一法万通(通过学习回溯+记忆化搜索是否可以去去除动态规划的学习),但是在这道题目的过程中,我发现动态规划会比回溯+记忆化搜索的处理方便很多;
可能这也是为什么需要将回溯和动态规划分别作为不同算法的原因
对于memo数组(记忆搜索)在回溯中的使用,我目前感觉到了阻碍;
可能还是需要进行动态规划的学习
3、但是我想要可以同时做到两种方法均适用对于这道题,然后后续的动态规划题目,只要理解了记忆搜索的用处,直接使用动态规划作答即可