暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件(base case)
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解
一定要学会怎么去尝试，因为这是动态规划的基础，这一内容我们将在提升班讲述
打印 n 层汉诺塔从最左边移动到最右边的全部过程
3层汉诺塔：
1 左 -> 右
2 左 -> 中
1 右 -> 中
3 左 -> 右
1 中 -> 左
2 中 -> 右
1 左 -> 右
[提示] 从局部出发
(1) 1 ~ i-1: start -> other
(2) i: start -> end
(3) 1 ~ i-1: other -> end
✅tested
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
int n = A.size();
process(n, A, C, B);
}
void processHanota(int n, vector<int>& from, vector<int>& to, vector<int>& other){
if(n == 1){
to.push_back(from.back());
from.pop_back();
return;
}
processHanota(n - 1, from, other, to);
to.push_back(from.back());
from.pop_back();
processHanota(n - 1, other, to, from);
}打印一个字符串的全部子序列，包括空字符串
void process(string& s, int i, string& res, vector<string>& str){
if(i == s.size()){
str.push_back(res);
return;
}
string resKeep = res;
resKeep += s[i];
process(s, i+1, resKeep);
string resNoInclude = res;
process(s, i+1, resNoInclude);
}- 节省空间做法
void process(string str, int i) {
if (i == str.size()) {
cout << str << endl;
return;
}
process(str, i + 1); //要当前字符
char tmp = str[i];
str[i] = 0;
process(str, i + 1); // 不要当前字符
str[i] = tmp;
}打印一个字符串的全部排列，要求不要出现重复的排列
[提示] 分支限界
✅tested
void swap(string& s, int i, int j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
vector<string> permutation(string s) {
vector<string> res;
process(s, 0, res);
return res;
}
// str[i...]范围上，所有的字符，都可以在i位置上，后续都去尝试
// str[0...i-1]范围上，是之前做的选择
// res: 所有的结果
void process(string s, int i, vector<string>& res) {
if (i == s.size()) {
res.push_back(s);
return;
}
vector<bool> visit;
for(int k = 0; k < 26; k++){
visit.push_back(false);
}
for (int j = i; j < s.size(); j++) {
if(!visit[s[j] - 'a']){ // 分支限界，指标上没有优化，常数项有优化
visit[s[j] - 'a'] = true;
swap(s, i, j);
process(s, i + 1, res);
swap(s, i, j);
}
}
}给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
【举例】 arr=[1,2,100,4]。
开始时，玩家A只能拿走1或4。如果开始时玩家A拿走1，则排列变为[2，100，4]，接下来玩家 B可以拿走2或4，然后继续轮到玩家A．
如果开始时玩家A拿走4，则排列变为[1，2，100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A...
玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。所以玩家A会先拿1，让排列变为［2，100，4］，接下来玩家B不管怎么选，100都会被玩家 A拿走。玩家A会获胜，分数为101。所以返回101。
arr=[1,100.2]。
开始时，玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100。所以返回100。
- 改为动态规划
参考：基础提升08
// 先手
int f(vector<int>& arr, int i, int j) {
if (i == j) {
return arr[i];
}
return max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
// 后手
int s(vector<int>& arr, int i, int j) {
if (i == j) {
return 0;
}
return min(f(arr, i + 1, j), f(arr, i, j - 1));
}
int win(vector<int>& arr) {
if (arr.size() < 1) {
return 0;
}
return max(f(arr, 0, arr.size() - 1), s(arr, 0, arr.size() - 1));
}给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？
void reverse(stack<int> s) {
if (s.empty()) {
return;
}
int i = f(s);
reverse(s);
s.push(i);
}
int f(stack<int> s) {
int result = s.top();
s.pop();
if (s.empty()) {
return result;
}
else {
int last = f(s);
s.push(result);
return last;
}
}规定1和A对应、2和B对应，3和C对应..
那么一个数字字符串比如“111”，就可以转化为“AAA”、“KA”和“AK”.
给定一个只有数字字符组成的字符串str，返回有多少种转化结果。
✅tested
// i 之前的位置如何转化已经做过决定
// i... 有多少种转化的结果
int translateNum(int num) {
string str = to_string(num);
return process(str, 0);
}
int process(string str, int i){
if(i == str.size() ){
return 1;
}
if(str[i] == '1'){
int res = process(str, i+1); // i 自己作为单独的部分，后续有多少种方法
if(i+1 < str.size()){
res += process(str, i+2); // i 和 i+1 作为单独的部分
}
return res;
}
if(str[i] == '2'){
int res = process(str, i+1);
// i 和 i+1 作为单独的部分且不超过25
if(i+1 < str.size() && (str[i+1] >= '0' && str[i+1] < '6')){
res += process(str, i+2);
}
return res;
}
//str[i] == '0' || '3' ~ '9'
return process(str, i+1);
}给定两个长度都为N的数组 weights 和 values，weights[i] 和 values[i] 分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？
-
尝试要求可变参数形式简单，数量少
-
背包问题
// i... 的货物自由选择，形成的最大价值返回
// alreadyweight: 之前的决定所达到的重量
int process(vector<int>& weights, vector<int>& values, int i, int alreadyweight, int bag) {
if (alreadyweight > bag) {
return 0;
}
if (i == weights.size()) {
return 0;
}
return max(process(weights, values, i + 1, alreadyweight, bag),
values[i] + process3(weights, values, i + 1, alreadyweight + weights[i], bag));
}N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。
给定一个整数n，返回n皇后的摆法有多少种。
n＝1，返回1。
n＝2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。
n＝8，返回92。
[时间复杂度]： O(n!)
✅tested
int totalNQueens(int n) {
vector<int> record; // record[i] -> 第i行的皇后，放在了第几列
for(int i = 0; i < n; i++){
record.push_back(-1);
}
return process(record, 0, n);
}
// record[0,...,i-1] 的皇后，任何两个皇后一定不共行、不共列、不共斜线
// 目前来到了第 i 行
// record[0,...,i-1] 表示之前的行，放过了哪些皇后
// n 代表整体一共有多少行
// res 表示摆完所有的皇后，合理的摆法有多少种
int process(vector<int>& record, int i, int n){
if(i == n){ // 终止行：最后一行再下一行的位置
return 1;
}
int res = 0;
for(int j = 0; j < n; j++){
if(isVaild(record, i, j)){
record[i] = j;
res += process(record, i+1, n);
}
}
return res;
}
// 当前i行的皇后，放在j列，会不会和之前(0...i-1)的皇后共行、共列或共斜线
bool isVaild(vector<int>& record, int i, int j){
for(int k = 0; k < i; k++){
if(j == record[k] || abs(record[k] - j) == abs(i - k)){
return false;
}
}
return true;
}- 常数时间的优化，使用位运算
// colLim 列的限制，1的位置不能放皇后，0的位置可以
// leftDiaLim 左斜线的限制
// rightDiaLim 右斜线的限制
int process(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
if (colLim == limit) { // base case
return 1;
}
int pos = 0;
int mostRightOne = 0;
// 所有候选皇后的位置都在pos上
pos = limit & (~(colLim | rightDiaLim | leftDiaLim));
int res = 0;
while (pos != 0) {
mostRightOne = pos & (~pos + 1);
pos = pos - mostRightOne;
res += process(limit,
colLim | mostRightOne,
(leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >> 1); // 此处要使用无符号右移
}
return res;
}
// 请不要超过32皇后问题
int totalNQueens(int n) {
if (n < 1 || n > 32) {
return 0;
}
// 生成二进制的数，8皇后问题，后8为是1
int limit = n == 32 ? -1 : (1 << n) - 1;
return process2(limit, 0, 0, 0);
}