以某个节点为开头
示例: [a, b , c, d , e]
以某个节点为开头的所有子序列,如 [a]
,[a, b]
,[ a, b, c]
… 再从以 b
为开头的子序列开始遍历 [b] [b, c]
。
通常用于暴力解法
子序列的长度
根据子序列的长度为标杆,如先遍历出子序列长度为 1 的子序列,在遍历出长度为 2 的等等。
leetcode 5. 最长回文子串 中的解法就用到了。
以结束节点为基准
以子序列的结束节点为基准,先遍历出以某个节点为结束的所有子序列,因为每个节点都可能会是子序列的结束节点,因此要遍历下整个序列,如: 以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。
第三种遍历方式 因为可以产生递推关系, 采用动态规划时, 经常通过此种遍历方式, 如 背包问题, 最大公共子串 , 这里的动态规划解法也是以 先遍历出 以某个节点为结束节点的所有子序列 的思路。
因为我们通常的惯性思维是以子序列的开头为基准,先遍历出以 a 为开头的所有子序列,再遍历出以 b 为开头的…但是动态规划为了找到不同子序列之间的递推关系,恰恰是以子序列的结束点为基准的。
动态规划一般都以结束节点为基准!