递推与递归笔记
分析递归用递归搜索树,有结果才会返回,树高与空间占有率有关,最多25层数
递归/dfs最重要的是顺序,不重不漏,1-n依次考虑每个数选或不选,保证深度优先(直往一条钻),选接下来的位置
注意顺序,回溯时候再写别的,先只针对一个过程,出了结果,任务完成才会回溯,注意回溯到上阶,不能用同层状态互推,先回到上阶,并把状态弄成不确定(分支是平级的,如何回到上阶状态),再推下一个状态
最后回到初始,返回整体
如何记录选和不选的状态,长度为n的数组记录每个数选还是不选
恢复现场,把当前位置改成0;
字典序,一个字符一个字符比较,看哪个ASCII大,只要一个大就停止比较,不管后面.
全排列:dfs最重要的是顺序,1.依次枚举每个位置应该放哪个数2.依次枚举每个数放哪个位置
深度优先代码只要想第一条路即刻
组合 dfs考虑顺序
dfs常用操作:减枝--减少递归次数
减枝,条件,下一个数不够了.继续向下,深度优先
(x-1)是当前位置前面的元素,n-start+1是剩余个数,加起来少于选择的数,减去