[数据结构与算法]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.从左往右的尝试模型

规定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);
}

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

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;
}

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

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 };

}

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);
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖