虽然动归没有确切的解题思路,可是以下的步骤却是常用的:
1.将原问题分解,缩小成为子问题.(与原题形式相同,不过规模变小)(例如数字三角形的子问题是求从倒数第二层走到倒数第一层时的最大值)将子问题不断化简,得出答案,当子问题可以完美解决,原问题便可完美解决。
2.设计该题的状态.一个状态的好坏直接影响到题解的正确性。状态的参数随题目而决定,在序列动归中一个序列往往是设计一个状态且通常是以某数结尾的一种状态(参考LCS和LIS)。
3.确定初始值及边界值.初始值及边界值在DP中往往起到一个题目突破口的作用(类似于递归函数的出口),从这一边界条件即可推出更多的状态。边界值往往是极端值(例如0,负数以及与题目范围(序列长度等)的较大值)
4.寻找状态转移方程(递推式).一个状态转移方程往往与先前设计的状态有关,状态转移方程的设计也是一道题中至关重要的环节。在一道题中,递推式可能不仅仅只有一个,也可能在有多个递推式,他们不同情况下递推式不同(此时便要分类讨论)(这种情况最常见),我们要做的就是:先将自己能想到的写下,再想想自己没有想到的情况(看看是否都考虑到)(所有可能的情况可能在不同的方面上),之后合并他们,最后将他们带入检验正确性(要注意动归的最优子结构&无后效性的特性)。