遍历方式的区别

以某个节点为开头

示例: [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 为开头的…但是动态规划为了找到不同子序列之间的递推关系,恰恰是以子序列的结束点为基准的。

动态规划一般都以结束节点为基准!


   转载规则


《遍历方式的区别》 锦泉 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录