layout: post
title: 算法笔记（四）从暴力递归到动态规划
description: 算法笔记（四）从暴力递归到动态规划
tag: 算法

机器人路径数

【题目】给定一个数N代表从1~N有N个位置，在起始位置1处只能往后走，结尾位置N处只能往前走，再给定机器人初始位置S和需要前往的位置E，如果规定必须在K步从S到达E，有多少种路径选择？

暴力递归

暴力递归的方法就是每次来到某个位置，尝试所有可以走的路，直至剩余步数为0.

int forceRecurRobotPath(int N, int E, int rest , int cur) {
	// 当恰好走，返回当前位置是否为E，是则找到一条路
	if (rest == 0) {
		return cur == E ? 1 : 0;
	}
	// 当来到1处只能往后走
	if (cur == 1) {
		return forceRecurRobotPath(N, E, rest - 1, cur + 1);
	}
	// 当来到N处只能往前走
	if (cur == N) {
		return forceRecurRobotPath(N, E, rest - 1, cur - 1);
	}
	// 中间位置既可以往前也可以往后
	return forceRecurRobotPath(N, E, rest - 1, cur + 1) + (N, E, rest - 1, cur - 1);
}

int robotPath1(int N, int E, int K, int S) {
	return forceRecurRobotPath(N, E, K, S);
}

memo表记忆搜索

上边暴力递归只有两个可变参数rest和cur，
这样暴力递归会重复计算很多之前计算过的过程。那么一个改进的思路就是以空间换时间，记录下每个可变参数的组合的计算结果到表中，每次如果遇到表中已有组合即可直接调用，称为记忆化搜索版本递归

按照这种思路，写出带记忆搜索的递归：
构建一个二维数组memo表，将可变参数rest和cur的所有组合找到的可行路径数都记录下：
rest的取值范围为[0, K]，cur的取值范围为[1,N]
vector<vector<int>> memo(N + 1, vector<int>(K + 1, -1));

// 带备忘录的递归
int memoRecurRobotPath(int N, int E, int rest, int cur, vector<vector<int>> memo) {
	if (memo[rest][cur] != -1) {
		return memo[rest][cur];
	}
	// 当恰好走完，返回当前位置是否为E，是则找到一条路
	if (rest == 0) {
		memo[rest][cur] = cur == E ? 1 : 0;
	}
	// 当来到1处只能往后走
	else if (cur == 1) {
		memo[rest][cur] = memoRecurRobotPath(N, E, rest - 1, cur + 1, memo);
	}
	// 当来到N处只能往前走
	else if (cur == N) {
		memo[rest][cur] = memoRecurRobotPath(N, E, rest - 1, cur - 1, memo);
	}
	else
	{
		// 中间位置既可以往前也可以往后
		memo[rest][cur] = memoRecurRobotPath(N, E, rest - 1, cur + 1, memo) + memoRecurRobotPath(N, E, rest - 1, cur - 1, memo);
	}
	return memo[rest][cur];
}
int robotPath2(int N, int E, int K, int S) {
	vector<vector<int>> memo(N + 1, vector<int>(K + 1, -1));
	return memoRecurRobotPath(N, E, K, S, memo);
}

动态规划

如果memo表结构数据之间有严格的依赖关系，那么可以将他改为动态规划的形式。
如下图，从递归过程上看，首先rest为0时，只有cur = 4（E），位置找到一种路径，红色框是出口位置。当cur来到1，它只能往后走，路径数依赖于f(rest - 1, cur + 1)，即它在memo表中右上方的结果，cur来到N，只能往前走，路径数依赖于f（rest-1，cur-1），即它在memo表中左上方的结果，而当cur在中间位置时，它依赖于f（rest-1，cur-1）+ f（rest-1，cur+1），左上+右上。由此，表中所有数据其实都可以由已经解计算出来，这是一种严格表结构。动态规划的过程就是，直接根据严格表的依赖关系，从表中已有解，一步一步得到全部的解，而所求必在表中。

动态规划版本：

int dpRobotPath(int N, int E, int K, int S) {
	vector<vector<int>> memo(K + 1, vector<int>(N + 1, -1));
	// rest = 0(when row = 0:) 先全赋值0, i = 0位置都-1，弃用
	for (int i = 1; i < N + 1; i++) {
		memo[0][i] = 0;
	}
	// 再将出口即终点处赋值为1
	memo[0][E] = 1;
	for (int rest = 1; rest <= K; rest++) {
		for (int cur = 1; cur <= N; cur++) {
			if (cur == 1) {
				memo[rest][cur] = memo[rest - 1][2];
			}
			else if(cur == N) {
				memo[rest][cur] = memo[rest - 1][N - 1];
			}
			else {
				memo[rest][cur] = memo[rest - 1][cur - 1] + memo[rest - 1][cur + 1];
			}
		}
	}
	return memo[K][S];
}

组成目标最少需要几枚硬币

【题目】给定正数数组，每个值代表一个硬币的币值，给定目标值target，问最少需要几枚硬币可以组成target。

暴力递归

每个硬币选或不选两种可能，这就可以列出所有的硬币的选择组合，将所有可以达成target的组合进行对比，选取硬币最少的组合。