今天理解了一点回溯的相关知识，记录一下。
链接：https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?answerType=1&f=discussion 来源：牛客网 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
看到这道题最开始想到的是，穷举出所有的可能情况，选择最大的，自然而然穷举，最简单的实现还是递归，我们假设，长度为7的绳子，剪一刀，出现的所有可能，分别是（1*6）、（2*5）、（3*4）、（4*3）、（5*2）、（6*1），观察一下，一组值，第一个用for实现，第二个值为总长减去第一个值，问题来了，那么剪完一刀后剩余的部分又该怎么剪，其实很简单，再按照上面的套路继续穷举呗，所以递归初步成型，就差退出条件，我们发现分到绳子还剩4的时候，绳子再剪的话就亏了，但是退出不应该==4的时候退出，因为我们发现绳子长度为5的时候，其实1*4 小于2*3。（通过特例去验证边界条件是最好的方法）。
class Solution { public: int back_track(int n) { // n <= 4, 表明不分，长度是最大的 if (n <= 4) { return n; } int ret = 0; for (int i = 1; i < n; ++i) { ret = max(ret, i * back_track(n - i)); } return ret; } int cutRope(int number) { // number = 2 和 3 时，分 2 段和分 1 段的结果是不一样的，所以需要特判一下 if (number == 2) { return 1; } else if (number == 3) { return 2; } return back_track(number); } };上面的代码超时了，确实，时间复杂度是n的阶乘。
我们发现，上面有好多重复计算，我们写一个备忘录，免去重复计算。
class Solution { public: int back_track(int n, vector<int> &mark) { if (n <= 4) { return n; } // 在方法一的基础上添加 if (mark[n] != -1) { return mark[n]; } int ret = 0; for (int i = 1; i < n; ++i) { ret = max(ret, i * back_track(n - i, mark)); } // 添加部分 return mark[n] = ret; } int cutRope(int number) { if (number == 2) { return 1; } else if (number == 3) { return 2; } // 添加部分 vector<int> mark(number+1, -1); return back_track(number, mark); } };在这里说一下，递归从函数调用点入栈之后，出栈的时候，基于本层栈的所有变量的值，从调用点之后，执行到函数大括号完，才能完整出栈。发现上面的代码和DFS很相似，按照上面画的递归图人肉执行一次就会发现回溯的奥秘。
