状态表示:从题目中推出某种性质,使得执行过程变成 一种状态 往下一个状态转移,并且具有无后效性(当前状态只与之前的状态有关,与未来的无关),那么考虑动态规划。
状态存储需要几维信息,开多少维数组 1. 如 271.杨老师的照相排列,每层阶梯站多少人,=> dp数组需要几维,每维下标是什么含义 2. 如 最长公共上升子序列 ,在最长公共子序列的状态表示基础上,加上以 b[j]为结尾,该信息不是决定划分dp数组几维用的,而会影响状态计算中集合的划分方式。