— By cuizhenkai
1.优化搜索顺序
从小到大排序， 优先尝试较长的木棍。
理解:
- 从最大开始可以较快的排除不可能的分支，避免
dfs进入比较深的树。 - 若从最小开始，则有可能前几根可以拼好，但是后面的不能满足条件，让
dfs进入了更深的层。
2. 排除等效冗余
A ) 限制先后加入一根原始木棍的长度递减。
理解:
- 先拼长度为 $x$，再拼为 $y$ 的木棍 $(x < y)$ 与反之是等效的。
B ) 对于当前原始木棒，记录最近一次尝试拼接的长度，如果失败回溯，不再向该木棒中添加一样长的木棍。
—— 这个比较好理解。
C ) 若在当前原始木棒中，尝试的第一根木棍就失败，那么该分支失败。
理解:
- 按照上面的剪枝，我们可以知道，对一根原始木棒，尝试的第一根木棍就失败，意味着其他的空木棒也必定失败。
D ) 若向一根原始木棒拼接了一根木棍后，恰好成功，但是下面的分支失败，那么此分支失败
理解:
- 用一根拼好比用若干根其他木棍拼好要更优，原因是长度小的木棍更灵活。
Code:
1 |
|