【算法ABC】动态规划 - 常见普通题型及状态表示

【算法ABC】动态规划 – 常见普通题型及状态表示

上一节我们讲了序列型动态规划,一点精髓就是动态规划最重要的是状态间的顺序(阶段划分)。这个顺序可能是题目给你的,也可能是需要自己转化出来的,确定了这个顺序之后,就可以类比序列型动态规划做了。可以说,熟练掌握了序列型动态规划,你就在代码层面和逻辑层面掌握了动态规划,其他所有题目都可以使用自己的智慧解答出来。 那么接下来,各位同学要做的就是多做题、多接触不同类型...
【算法ABC】动态规划 - 序列型

【算法ABC】动态规划 – 序列型

序列型动态规划 这类题目上来一定丢给你一个类似序列东西,比如说一个数列 {a_n},一个字符串 S或者说是一排房子。总之就是给你一堆东西,它们显式或者隐式地存在一种从前先后的顺序。 对于这种类型的题目,阶段地划分就按照序列从前往后的位置顺序进行,考虑到了第 i 个位置,那么就位于阶段 i,结下来要往阶段 i+1 转移。状态设计的时候,也会将序列中的位置作为状...