DFS 、动态规划、回溯法、递归之间的关系是啥( 二 )
回溯是 dfs 的一种表现形式。除此之外，dfs 还有另一种表现形式，它使用的是局部变量，类似于记忆；而回溯使用的是全局变量。dfs 一般都是以递归形式呈现的。因为这样清楚。（dp 有时用递归也是因为如此。）除非内存不够，一般不会手动写栈。
■网友
用几个例子把。
1.整数分解为若干项之和.：
将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2 7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2 7=1+2+4;7=1+3+3;7=1+6;7=2+2+3 7=2+5;7=3+4;7=7
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N?1??={n?1??,n?2??,?}和N?2??={m?1??,m?2??,?}，若存在i使得n?1??=m?1??,?,n?i??=m?i??，但是n?i+1??\u0026lt;m?i+1??,则N?1??序列必定在N?2??序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
解题思路：
利用压栈。数组记录下所有用过的数字，然后利用递归，看看这样能不能再加上别的数。
动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。 @帅地 的文章说的很好。
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？#include\u0026lt;stdio.h\u0026gt;//等式右边的值为非递减序列，进行递归的值应该小于N的一半。要不然会出现4+3//然后还得注意每行最后一个输出都是不带";"int N;int s; // 存放划分结果，这里用数组。int top = -1; // 数组指针 int count = 0; // 统计输出的次数 int sum = 0; // 拆分项累加和 void division (int i);int main (){ scanf ("%d", \u0026amp;N); division (1); return 0; }void division (int i) {//拆分 \tint k; if (sum == N) { //如果刚好等于N ，输出 count ++; //计数 printf("%d=", N); // 输出开头 for (k=0; k\u0026lt;top; k++) { printf("%d+", s); //输出栈内所有。 } if (count%4 == 0 || s == N) { //输出 7=7 或者输出4个了 printf("%d\", s); } else { printf("%d;", s); } return; } // 输出部分 if (sum \u0026gt; N) { //如果拆分累加，加上别的没用过的数超过了N，那就退回去。（或许就是回溯法？） return; } for (int j=i; j\u0026lt;=N; j++) { s = j; //记录top sum += j; //sum累加 division (j); //尝试递归 sum -= j; // 减去 top --; //出栈 } }输出全排列
请编写程序输出前n个正整数的全排列（n\u0026lt;10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。
例如 3 输出 123 132 213 231 312 321 #include\u0026lt;stdio.h\u0026gt;int N;int s; // 存放结果，这里用数组int a ;int count = 0; // 统计输出的次数 void division (int i);int main (){ scanf ("%d", \u0026amp;N); division (0); return 0; }void division (int i) {//拆分 \tint j,k; if (i == N) {\t\tfor (k=0; k\u0026lt;N; k++) {\t\t\t\tprintf("%d", s); //输出栈内所有。\t\t\t}\t\t\tprintf("\"); } // 输出部分 for (j=1; j\u0026lt;=N; j++) { \t\tif(a==0){ // 执行，have saved就过。\t\t\ts = j; //记录\t\t\ta =1 ; //j 已经保存\t\t\tdivision (i); //尝试递归\t\t\t a=0 ;// 这个数字输出过后，返回上一层继续递归。\t\t\ti --; //出栈\t\t} } }
推荐阅读
- 动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢
- 怎样做内部审计系统，用于数据泄漏后的回溯
- bfs,dfs怎样保存路径?
- 怎样基于fastdfs搭建缩略图服务器
- 为啥hadoop 不直接采用 lustre 而要用hdfs
- 强化学习内动态规划中的算例求解
- 啥使用用广度搜索（bfs）啥时候用深度搜索（dfs）
- spark读取hdfs文件,block与executor?
- [焊接]特写：走近昆山“90后”科技创新“天团”
- 动态规划和贪心法的区别