分治法是解决规模庞大的问题的很好的思路，他通过降低问题的规模，形成若干个规模更小但形式相同的子问题，进行递归求解。在求解过后，将各个子问题的解合并起来，形成原问题的解。
那么它的大致流程主要分成三步：
分解（Divide）将大规模的问题分解成若干个规模更小但形式相同的子问题
解决（Conquer）如果当前问题的规模足够小，并可以直接解决的话，那么直接解决并返回解。否则，继续进行分解并递归求解分解后的子问题。
合并（Merge）将各个子问题合并，最终形成原问题的解。
所以，明确了三步之后，还要明确一件事件——实现方式：递归法。
举个例子
f(n) = f(n - 1) + f(n - 2)
蓝色 代表当前搜索路走过的路径节点
白色 代表没有搜索走过的节点
红色 代表已经搜索过的节点，不可以再走
左子树 代表走一步
右子树 代表走两步
回溯
如果你理解了下图的运动轨迹，我想差不多对于回溯的搜索过程就基本了解了。所以，你可以找到其他回溯点么？
理解了上图的运动轨迹后，那么，代码是什么样子呢？
#include </iostream><iostream>
using namespace std;
//int count 方案总数
// int target 目标—— 剩余的台阶数
void dfs(int& count, int target) {
// 边界条件
if (target < = 2) {
count += target; // 当剩余一个台阶是即累加一种方案，剩余两个台阶时累加两种方案
return;
}
// 下面是两个基本点选择一步和选择两步
// 选择一步
dfs(count, target - 1);
// 选择两步
dfs(count, target - 2);
}
int main() {
int count = 0;
dfs(count, 4);
cout<<count<<endl;
return 0;
} 剩余一个台阶时，累加一种方案
剩余两个台阶时，累加两种方案
选择走一步
选择走两步
动态规划（Dynamic Programming）
dp[i] = dp[i - 1] + dp[i - 2]i代表当前问题的规模，即所需要跳过的台阶数。dp[i]代表的是跳过i个台阶的方案数量
其实，看到这里我们会发现，根据动态规划和分治法的思路，其解决方案大致是一样的，这一点从其递归关系式和状态转移方程可以看出来。这也是我在前文说到的，分治法与动态规划有交集的一种情况的具体体现。
递归法
迭代法
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 4;
vector<int> dp(n + 1, 0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < = n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout<<dp[n]<<endl;
return dp[n];
} 总结
递归 动态规划、分治法与回溯法都可以使用递归的方式来实现
子问题 分治法、回溯法与动态规划都利用了子问题的解进行决策
题目：给定无序整型数组 `nums = [1,2,4,2,-2,10]`，寻找所有的排列情况。即 `An1，An2...Ann`
全部评论