递归
函数中自己调用自己经典例题:汉诺塔
递归思想-自顶向下
1.将一个问题规模变小
2.利用规模化到最小的子问题得出结果
汉诺塔问题规模为1时就可以直接移动3.用子问题的解得出结果
可以将递归函数,看成已经实现好的,可以直接用来解决子问题 然后考虑根据子问题的解和当前面对的情况,得出答案递归函数结构模板
暂时无法在飞书文档外展示此内容 示例:力扣247 中心对称数递归时间复杂度分析
1.迭代法
计算时间执行函数T(n)
以汉诺塔为例2.公式法
额外时间:
例如归并排序中,递归处理完两边数组后,进行合并操作的时间,就是f(n)递归部分复杂度公式:
三种情况
回溯 Backtracking
尝试 -> 扩展 -> 撤销(回溯)算法概念
回溯算法是一种试探算法 与暴力搜索的区别: 回溯是一步步向前试探,对每一步探测的情况进行评估,再决定是否深入,可以避免走一些弯路 回溯算法的核心: 出现非法情况时,可以撤销更改,回退到之前的情景 想要采用回溯算法,就必须保证:每次都有多种尝试的可能回溯算法程序模板
1.判断当前情况是否非法,若非法直接返回
2.判断递归是否应该结束,若结束,保存当前结果并返回
3.遍历所有可能出现的情况,将其加入尝试容器,并进行递归扩展
4.递归完毕后,立即回溯,取消前一步进行的尝试(将之前尝试的数从尝试容器中踢出)
示例程序:子集枚举class Solution {
public:
vector<int> temp;
vector<vector<int>> ans;
void dfs(int cur,vector<int>& nums) //参数:当前位置,原数组
{
if(cur == nums.size()) //若已到达数组尽头,停止递归
{
ans.push_back(temp); //将临时数组装进答案列表
return;
}
//进行两种可能情况的分支递归
temp.push_back(nums[cur]); //若当前数为选中状态
dfs(cur+1,nums); //此分支下递归,考虑后一个数字是否选中
temp.pop_back(); //若当前数为不选中状态
dfs(cur+1,nums); //此分支下递归,考虑后一个数字是否选中
}
vector<vector<int>> subsets(vector<int>& nums)
{
dfs(0,nums); //从头开始考虑每一个数是否选中
return ans;
}
};
标签:递归,nums,复杂度,算法,vector,回溯
From: https://www.cnblogs.com/jk-2048/p/18030018