回溯法

[TOC]

回溯法可以看成蛮力法的升级版,它从解决问题每一步的所有可能选项里系统地选择出一个可行的解決方案。

回溯法非常适合由多个步骤组成的问题,并且每个步骤都有多个选项。

当我们在某一步选择了其中一个选项时, 就进入下一步, 然后又面临新的选项。我们就这样重复选择, 直至到达最终的状态。

回溯法

如果面试题要求在二维数组(可能具体表现为迷宫或者棋盘等)上搜索路径, 那么我们可以尝试用回溯法。通常回溯法很适合用递归的代码实现。只有当限定不可以用递归实现的时候, 我们再考虑用栈来模拟递归的过程。

试题12:矩阵中的路径