5.递归和动态规划

1.汉诺塔问题（递归）

//解法1
void rightTomid(int);
void rightToleft(int);
void leftTomid(int);
void midToleft(int);
void midToright(int);
void leftToright(int);
void rightTomid(int n) {
	if (n == 1) {
		cout << "move 1 from right to mid" << endl;
		return;
	}
	rightToleft(n - 1);
	cout << "move " << n << "from right to mid" << endl;
	leftTomid(n - 1);
}

void rightToleft(int n) {
	if (n == 1) {
		cout << "move 1 from right to left" << endl;
		return;
	}

	rightTomid(n - 1);
	cout << "move " << n << "from right to left" << endl;
	midToleft(n - 1);
}

void midToleft(int n) {
	if (n == 1) {
		cout << "move 1 from mid to left" << endl;
		return;
	}
	midToright(n - 1);
	cout << "move " << n << "from mid to left" << endl;
	rightToleft(n - 1);
}

void midToright(int n) {
	if (n == 1) {
		cout << "move 1 from mid to right" << endl;
		return;
	}
	midToleft(n - 1);
	cout << "move " << n << "from mid to right" << endl;
	leftToright(n - 1);
}

void leftTomid(int n) {
	if (n == 1) {
		cout << "move 1 from left to mid" << endl;
		return;
	}
	leftToright(n - 1);
	cout << "move " << n << " from left to mid" << endl;
	leftTomid(n - 1);
}

void leftToright(int n) {
	if (n == 1) {
		cout << "Move 1 from left to right" << endl;
		return;
	}
	leftTomid(n-1);
	cout << "Move " << n << " from left to right" << endl;
	midToright(n - 1);
}

void test02(int n) {
	leftToright(n);
}


//---------------------------递归2--------------------

void test02_1_1(int n, string from, string to, string other) {
	if (n == 1) {
		cout << "move 1 from " << from << "to " << to << endl;
		return;
	}
	test02_1_1(n - 1, from, other, to);
	cout << "move " << n << " from " << from << " to" << endl;
	test02_1_1(n - 1, other, to, from);
}

void test02_1(int n) {
	test02_1_1(n, "left", "right", "mid");
}

2.逆序一个栈 不申请额外的数据结构

int fun(stack<int>& sta) {
	int num = sta.top();
	sta.pop();
	if (sta.empty()) {
		return num;
	}
	int last = fun(sta);
	sta.push(num);
	return last;
}

void test03_1(stack<int>& sta) {
	if (sta.empty()) {
		return;
	}
	int num = fun(sta);
	test03_1(sta);
	sta.push(num);
}

void test03() {
	stack<int> sta;
	sta.push(1);
	sta.push(2);
	sta.push(3);
	sta.push(4);
	sta.push(5);
	test03_1(sta);

	while (!sta.empty()) {
		int tmp = sta.top();
		sta.pop();
	}
}

3.打印一个字符串的全部子序列，要求不出现重复字面值的子序列

set<string> restr;
string tmp;

void test04_1(string& str, int index) {
	if (tmp.size() <= str.size()) {
		restr.insert(tmp);
	}
	else {
		return;
	}

	for (int i = index; i < str.size(); i++) {
		tmp.push_back(str[i]);
		test04_1(str, i + 1);
		tmp.pop_back();
	}

}

void test04() {
	string str = "aac";
	test04_1(str, 0);
	for (const auto& s : restr) {
		cout << s << endl;
	}
}

4.打印一个字符串的全部排列,且不出现重复字面值的排列

set<string> vstr5;
string str5;
void test05_1(string& str, vector<bool> flag) {
	if (str5.size() == str.size()) {
		vstr5.insert(str5);
		return;
	}

	for (int i = 0; i < str.size(); i++) {
		if (flag[i] == true) continue;
		flag[i] = true;
		str5.push_back(str[i]);
		test05_1(str, flag);
		str5.pop_back();
		flag[i] = false;
	}
}

void test05() {
	string str = "aac";
	vector<bool> flag(str.size(), false);
	test05_1(str, flag);
	for (const auto& s : vstr5) {
		cout << s << endl;
	}
}

5.从左往右的尝试模型

5.1递归版本

规定1和A对应 2和B对应 3和C对应。。。则一个字符串比如“111”就可以转化为"AAA"，“KA”和“AK”
给定一个只有数字字符组成的字符串str,返回有多少种转化结果

int test06_1(string& str, int index) {
	if (index == str.size()) {
		return 1;
	}
	if (str[index] == '0') {
		return 0;
	}

	if (str[index] == '1') {
		int ret = test06_1(str, index + 1);
		if (index + 1 < str.size()) {
			ret += test06_1(str, index + 2);
		}
		return ret;
	}

	if (str[index] == '2') {
		int ret = test06_1(str, index + 1);
		if (index + 1 < str.size() && (str[index] + 1 >= '0' && str[index + 1] <= '6')) {
			ret += test06_1(str, index + 2);
		}
		return ret;
	}

	return test06_1(str, index + 1);

	if (str[index] >= '1' && str[index] <= '9') {
		
	}
}

void test06() {
	string str = "11256";
	test06_1(str, 0);
}

5.2动态规划版本

int test13_1(string str) {
	vector<int> dp(str.size() + 1);
	dp[str.size()] = 1;
	for (int i = str.size() - 1; i >= 0; i--) {
		if (str[i] == '0') {
			dp[i] = 0;
		}
		else if (str[i] == '1') {
			dp[i] = dp[i + 1];
			if (i + 1 < str.size()) {
				dp[i] += dp[i + 2];
			}
		}
		else if (str[i] == '2') {
			dp[i] = dp[i + 1];
			if (i + 1 < str.size() && (str[i] + 1 >= '0' && str[i + 1] <= '6')) {
				dp[i] += dp[i + 2];
			}
		}
		else {
			dp[i] = dp[i + 1];
		}
	}
	return dp[0];
}

6.给定两个长度都为N的数组weights和values weights[i]和values[i]分别代表i号物品的重量和价值 给定一个正数bag，表示一个载重bag的袋子，所装物品不能超过这个重量,返回能装下的最多的价值 6.1递归版本

int test07_1(vector<int>& weights, vector<int>& values, int index, int bag, int cur) {
	if (cur > bag) return -1;
	if (index == weights.size()) {
		return 0;
	}
	int p1 = test07_1(weights, values, index + 1, bag, cur);
	int p2 = test07_1(weights, values, index + 1, bag, cur + weights[index]);
	if (p2 != -1) {
		p2 = values[index] + p2;
	}
	return max(p1, p2);

}

void test07() {
	vector<int> vec1{ 1,2,3 };
	vector<int> vec2{ 1,2,3 };
	cout << test07_1(vec1, vec2, 0, 3, 0) << endl;
}

6.2动态规划版本

int test12_1(vector<int>& weights, vector<int>& values, int bag) {
	int size = weights.size();
	vector<vector<int>> dp(size + 1, vector<int>(bag + 1));
	for (int i = size - 1; i >= 0; i--) {
		for (int j = 0; j <= bag; j++) {
			dp[i][j] = dp[i + 1][j];
			if (j >= weights[i]) {
				dp[i][j] = max(dp[i][j], values[i] + dp[i + 1][j - weights[i]]);
			}
		}
	}

	return dp[0][bag];

}

7.给定一个整数数组arr，代表数值不同的纸牌拍成一条线，玩家A和玩家B都绝顶2聪明，玩家A和玩家B依次拿走每张纸牌，每次都只能拿走最左或最有的纸牌，返回最后获胜者的分数 7.1递归版本

int test08_1(vector<int>& vec, int left, int right);
int test08_2(vector<int>& vec, int left, int right) {
	if (left == right) {
		return 0;
	}
	return min(test08_1(vec, left + 1, right), test08_1(vec, left, right - 1));
}

int test08_1(vector<int>& vec, int left ,int right) {
	if (left == right) {
		return vec[left];
	}
	return max(vec[left] + test08_2(vec, left + 1, right), vec[left] + test08_2(vec, left, right - 1));
}

void test08() {
	vector<int> vec{ 1,2,3,4,5 };

}

7.2动态规划版本

int test14_1(vector<int>& vec) {
	vector<vector<int>> dp1(vec.size(), vector<int>(vec.size()));
	vector<vector<int>> dp2(vec.size(), vector<int>(vec.size()));
	for (int i = 0; i < dp1.size(); i++) {
		dp1[i][i] = vec[i];
	}

	for (int i = 1; i < vec.size(); i++) {
		int l = 0;
		int r = i;
		while (l < vec.size() && r < vec.size()) {
			dp1[l][r] = max(vec[l] + dp2[l + 1][r], vec[l] + dp2[l][r - 1]);
			dp2[l][r] = min(dp1[l + 1][r], dp1[l][r - 1]);
			l++, r++;
		}
	}

	return std::max(dp1[0][vec.size() - 1], dp2[0][vec.size() - 1]);
}

8.N皇后问题

vector<vector<string>> res9;
vector<string> str9;
bool isVaild(int row, int col, vector<string>& s, int n) {
	for (int i = 0; i < row; i++) {
		if (s[i][col] == 'Q') return false;
	}
	for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
		if (s[i][j] == 'Q') return false;
	}
	for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
		if (s[i][j] == 'Q') return false;
	}
	return true;
}

void backtracking(int n, int startIndex) {
	if (startIndex == n) {
		res9.push_back(str9);
		return;
	}

	for (int i = 0; i < n; i++) {
		if (isVaild(startIndex, i, str9, n)) {
			str9[startIndex][i] = 'Q';
			backtracking(n, startIndex + 1);
			str9[startIndex][i] = '.';
		}
	}
}

vector<vector<string>> test09(int n) {
	str9 = vector<string>(n, string(n, '.'));
	backtracking(n, 0);
	return res9;
}

9.假设有一排数字，记为1-N， N一定大于或等于2，开始时机器人在其中M的位置上，如果机器人来到1位置，那么下一步只能往右来到2位置，如果机器人来到N位置，那么下一步只能往左来到N-1位置，如果机器人来到中间位置，那么下一步可以往左走也可以往右走，规定机器人必须走K步,最终能来到P位置的方法有多少种

int test10_1(vector<int>& vec, int index, int k, int p) {
	if (k == 0) {
		return index == p ? 1 : 0;
	}
	if (index == 0) {
		return test10_1(vec, index + 1, k - 1, p);
	}
	if (index == vec.size() - 1) {
		return test10_1(vec, index - 1, k - 1, p);
	}
	return test10_1(vec, index + 1, k - 1, p) + test10_1(vec, index - 1, k - 1, p);
	
}

void test10() {
	vector<int> vec{ 2,6,8,6,4,7,1,2,3 };
	test10_1(vec, 0, 5, 3);
}

10.上一道题的记忆化搜索

int test11_1(vector<int>& vec, int index, int k, int p, vector<vector<int>> dp) {
	if (dp[index][k] != -1) {
		return dp[index][k];
	}
	if (k == 0) {
		dp[index][k] = index == p ? 1 : 0;
		return dp[index][k];
	}
	if (index == 0) {
		dp[index][k] = test11_1(vec, index + 1, k - 1, p, dp);
		return dp[index][k];
	}
	if (index == vec.size() - 1) {
		dp[index][k] = test11_1(vec, index - 1, k - 1, p, dp);
		return dp[index][k];
	}
	dp[index][k] = test11_1(vec, index + 1, k - 1, p, dp) + test11_1(vec, index - 1, k - 1, p, dp);
	return dp[index][k];
}

void test11() {
	vector<int> vec{ 2,6,8,6,4,7,1,2,3 };
	vector<vector<int>> dp(vec.size() + 1, vector<int>(4, -1));

	test11_1(vec, 0, 5, 3, dp);
}

11.给定一个数组，数组中每一个位置的值都是一个货币的面值，每一种面值都可以使用任意张，数组中都是正数且无重复值，给定一个目标值，用给定数组中的数字，有多少种方法可以把目标值得出来。 11.1递归版本

int test15_1(vector<int>& vec, int index, int target) {
	if (target < 0) {
		return 0;
	}
	if (index == vec.size()) {
		return target == 0 ? 1 : 0;
	}
	int ways = 0;
	for (int i = 0; i * vec[index] <= target; i++) {
		ways += test15_1(vec, index + 1, target - (i * vec[index]));
	}
	return ways;
}

11.2动态规划版本

int test15_2(vector<int>& vec, int target) {
	if (vec.size() == 0 || target < 0) {
		return 0;
	}
	vector<vector<int>> dp(vec.size() + 1, vector<int>(target + 1));
	dp[vec.size()][0] = 1;

	for (int i = vec.size()-1; i >= 0; i--) {
		for (int rest = 0; rest <= target; rest++) {
			int ways = 0;
			for (int j = 0; j * vec[i] <= rest; j++) {
				ways += dp[i + 1][rest - (j * vec[i])];
			}
			dp[i][rest] = ways;
		}
	}
	return dp[0][target];
}

int test15_3(vector<int>& vec, int target) {
	if (vec.size() == 0 || target < 0) {
		return 0;
	}
	vector<vector<int>> dp(vec.size() + 1, vector<int>(target + 1));
	dp[vec.size()][0] = 1;

	for (int i = vec.size() - 1; i >= 0; i--) {
		for (int rest = 0; rest <= target; rest++) {
			dp[i][rest] = dp[i + 1][rest];
			if (rest - vec[i] >= 0) {
				dp[i][rest] += dp[i][rest - vec[i]];
			}
		}
	}
	return dp[0][target];
}

12.给定一个字符串str，给定一个字符串类型的数组arr，arr里的每一个字符串代表一张贴纸，使用arr里的字符拼凑出最少使用多少张贴纸完成任务（leetcode691）

//搜索拼凑target需要的最少贴纸数量
int dfs(unordered_map<string, int>& strStickerCnt, vector<vector<int>>& myStickers, string target) {
	if (strStickerCnt.count(target)) {
		//如果target已经搜索过，直接返回
		return strStickerCnt[target];
	}
	int minRes = INT_MAX, stickersSize = myStickers.size();
	//统计target中各个字符出现的次数
	vector<int> tar(26, 0);
	for (char ch : target) {
		tar[ch - 'a'] += 1;
	}
	//尝试使用每一个sticker
	for (int i = 0; i < stickersSize; ++i) {
		//如果当前sticker中没有target[0]这个字符则剪枝,并且能防止死循环
		if (myStickers[i][target[0] - 'a'] == 0) {
			continue;
		}
		//使用当前sticker，nowTarget为运用贴纸后剩余的字母
		string nowTarget = "";
		for (int j = 0; j < 26; j++) {
			if (tar[j] - myStickers[i][j] > 0) {
				nowTarget += string(tar[j] - myStickers[i][j], 'a' + j);
			}
		}
		//搜索nowTarget字符串需要最少贴纸数
		int tempRes = dfs(strStickerCnt, myStickers, nowTarget);
		//更新target字符串需要的最少贴纸数
		if (tempRes != -1) {
			minRes = min(minRes, 1 + tempRes);
		}
	}
	strStickerCnt[target] = (minRes == INT_MAX ? -1 : minRes);//标记target已经搜索过
	return strStickerCnt[target];
}

int test16(vector<string>& stickers, string target) {
	int stickersSize = stickers.size();
	unordered_map<string, int> strStickerCnt;//strStickerCnt[str]表示的字符串str需要的最少贴纸数量
	vector<vector<int>> myStickers(stickersSize, vector<int>(26, 0));//各个贴纸中各个字母出现的次数
	//统计每一个sticker中各个字符出现的次数
	for (int i = 0; i < stickersSize; ++i) {
		for (char ch : stickers[i]) {
			myStickers[i][ch - 'a'] += 1;
		}
	}
	strStickerCnt[""] = 0;//初始化，空字符串不需要贴纸
	return dfs(strStickerCnt, myStickers, target);
}

13.两个字符串的最长公共子序列问题

int test17(string& s1, string& s2) {
	if (s1.size() == 0 || s2.size() == 0) {
		return 0;
	}

	vector<vector<int>> dp(s1.size(), vector<int>(s2.size()));
	for (int i = 0; i < s2.size(); i++) {
		if (s1[0] == s2[i]) {
			dp[0][i] = 1;
		}
		if (i > 0) dp[0][i] = max(dp[0][i], dp[0][i - 1]);
	}

	for (int i = 0; i < s1.size(); i++) {
		if (s1[i] == s2[0]) {
			dp[i][0] = 1;
		}
		if (i > 0) dp[i][0] = max(dp[i][0], dp[i - 1][0]);
	}

	for (int i = 1; i < s1.size(); i++) {
		for (int j = 1; j < s2.size(); j++) {
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

			if (s1[i] == s2[j]) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
			}
		}
	}

	return dp[s1.size() - 1][s2.size() - 1];
}

14.给定一个数字arr和参数a和参数b，arr代表每个人准备刷杯子的时间，a代表洗一个杯子耗费的时间，b代表杯子自行挥发干净所用的时间,返回让所有咖啡杯边干净的最早完成时间* 14.1 递归

int test18_1(vector<int>& drinks, int a, int b, int index, int washLine) {
	if (index == drinks.size() - 1) {
		return min(max(washLine, drinks[index]) + a, drinks[index] + b);
	}

	int wash = max(washLine, drinks[index]) + a;
	int next1 = test18_1(drinks, a, b, index + 1, wash);
	int p1 = max(wash, next1);
	int dry = drinks[index] + b;
	int next2 = test18_1(drinks, a, b, index + 1, washLine);
	int p2 = max(dry, next2);
	return min(p1, p2);
}

14.2 DP

int test18_2(vector<int>& drinks, int a, int b) {
	if (a >= b) {
		return drinks[drinks.size() - 1] + b;
	}

	int N = drinks.size();
	int limit = 0;
	for (int i = 0; i < N; i++) {
		limit = max(limit, drinks[i]) + a;
	}

	vector<vector<int>> dp(N, vector<int>(limit + 1));
	for (int i = 0; i <= limit; i++) {
		dp[N - 1][i] = min(max(i, drinks[N - 1]) + a, drinks[N - 1] + b);
	}

	for (int i = N - 2; i >= 0; i--) {
		for (int j = 0; j <= limit; j++) {
			int p1 = INT_MAX;
			int wash = max(j, drinks[i]) + a;
			if (wash <= limit) {
				p1 = max(wash, dp[i + 1][wash]);
			}
			int p2 = max(drinks[i] + b, dp[i + 1][j]);
			dp[i][j] = min(p1, p2);
		}
	}

	return dp[0][0];
}