讨论/算法和数据结构/动态规划该怎么学?/
动态规划该怎么学?

大佬们,怎么才能掌握动态规划。

展开讨论
共 7 个讨论

看过最难的dp题无非就是戳气球,砸鸡蛋这种。你在第二层,你以为它是第一层,实际上它却是第芜层。反正我学不会,看答案看一道会做一道。

3

个人的一点感想:
1、找 动态规划 标签的题,多刷一些。然后就想到一个问题怎样拆分成子问题(递归)。想到递归就成功了 80% 了!
2、能用递归,就要想到动态规划(python:简单!@lru_cache(None))。
3、动态规划本身不难,难的是出题人在动态规划上加上了一些乱七八糟的东西,让人一眼看不出来,这需要经验。
4、所以还是多做题,你会爱上动态规划!有些题目,本来是暴力算法,用动态规划稍微一改就成了!反而一些所谓的 “贪心算法” “数学” 标签的题,吊打了我的智商。。

1

个人愚见,理解DP的思想,然后做题;我以前也觉得DP的题目头疼,多做多练之后会慢慢发现其中的共性,但是DP没有万能公式。再者说背包九讲和股票买卖这两个经典的DP问题,你看题解总能看到里面的巧计妙解,但是核心都是理解状态定义,什么是该用常量,一维数组,二维数组或者是三维数组等定义一个什么样的状态;然后如何进行状态转移;什么时候要进行状态压缩等等。所以说只有多做多练。

我看完数据结构里也没讲到动态规划

动态规划千变万化,像背包这样的常见经典题型可以通过练习提高熟练度,但是出题人有一万种方式出出来一道很难的动态规划题。

君不见,强如tourist,也有做不出来的DP题。

掌握常见的动态规划套路即可,不必试图掌握所有的题型。

之前看过动态规划,感觉好难