DynamicProgramming动态规划整理

整理一下刷题过程中的一些想法,方便以后高效复习,动态规划部分整理如下:

主要的思路有如下几种:

基础类型

  • 只需要写出i和i-1之间的状态转移方程即可,没有任何额外操作的行为,比如:

中间变量类型

  • 需要额外借助第三方变量进行中间值判断的:

定制判断类型

倒叙逆向类型

  • 174. 地下城游戏,状态转移方程是:dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
    反方向的的递归,比较打破常规思维

循环判断类型

  • 在dp的基础上需要再遍历已经扫过的数组。此类方法的复杂度一般较高:
    • 279. 完全平方数,状态转移方程是:
      1
      2
      3
      while i - j ** 2 >= 0:
      dp[i] = min(dp[i], dp[i - j ** 2] + 1)
      j += 1

预处理类型

  • 740. 删除与获得点数
    这题麻烦在预处理每一个值,因为值有可能重复:
    1
    2
    3
    target = [0] * (max(nums) + 1)
    for num in nums:
    target[num] += num

之后的转移方程反而非常简单:d[i] = max(d[i - 1], d[i - 2] + target[i])

技巧类型

这题在于要想到把字符转化对应的ASCII码,转移方程:array[ord(c)-ord("a")]=sum(array)+1,除此之外还需要想到新增一个字母等于当前所有字母后面可加+单独自身,这个方程确实非常非常有技巧


以上为LeetCode中比较有代表性的一些题目,把这些搞懂之后可以解决绝大多数dp的类似题型,以2020校招为例:

携程 - Deep learning Engineer

给定一个时刻表,根据目的地进行分组,同一个目的地必须尽可能的多分,不能打乱顺序,比如aabbcddc,需要分成aa|bb|cddc,而不能分成aabb|cddc,因为这种情况下不是最多,也不能分成aa|bb|c|dd|c,因为相同的c没有被分在一起;求分组个数;

这题就是典型的循环判断类型+中间变量类型,需要储存历史遍历结果并多次查询,代码解答

Tencent - Deep learning Engineer
花匠摆花问题,两个坑:
1.用traceback的就直接gg,比如我
2.dp[i]为当前的长度为i的可摆放个数,dp[i] = dp[i-1]+dp[i-k]为状态转移矩阵,更多解释看代码注释

这题就是简单的基础类型,唯一难的地方是要想到i-k这个dp结果

Dynamic Programming 动态规划就给大家整理到这,如果大家想看更多的数据结构问题,可以关注一下我的Github,希望有所帮助。

欢迎大家关注我的个人bolg知乎,更多代码内容欢迎follow我的个人Github,如果有任何算法、代码、转行疑问都欢迎通过邮箱发消息给我。

打赏的大佬可以联系我,赠送超赞的算法资料