算法<初级> - 第五章 递归与动规相关问题（完结）

<一>递归和动态规划

• 暴力递归

  • 转化为规模缩小了的同问题的子问题 - 时间复杂度O(2ⁿ-1)

  • 有明确的边界条件（base case） - 先写base case，再写问题递归的过程

  • 有得到子问题结果后决策过程

  • 不记录每个子问题的解 - 每次求解子问题都交给递归去解决，不会在全局保存子问题的解（与动规形成对比）

• 动态规划DP

  • 从暴力递归中延申 - 过程中还经历过<记忆化搜索>，相当于暴力递归+cache缓存(用hashmap实现)，他并没有状态方程依赖，只是单纯的记忆并给出。

  • 记录每个问题的子问题，避免重复计算（与暴力递归之间最大的区别）

    • eg. 求n!问题：暴力递归f(n)=n * f(n-1)；动规使用数组存储，f[n] = n * f[n-1]，这样记录每个子问题避免了重复计算

  • 把暴力递归的过程，抽象成状态转移 - 子函数的嵌套调用转换成数组序号的关系(依赖)

  • 并且存在化简状态转移使其更简洁的过程（状态方程的化简）

    • eg. 格子值等于上一行该格子位置上前数Σ；状态方程(A+B+C) = A+B+C；化为动规就是将上一行该格子位置上前数组索引Σ - 再化简就是该格子值等于上格子值+左格子值；状态方程(A+B+C) = ((A+B)+C)，(A+B)是左格子，C是上格子

题目七：二维数组最小路径和

• 题目表述：给予一个二维数组，从左上走到右下，每步只能向下或者向右，返回最短路径和。

• 思想：某点的最短路径和，是min(上面格子最短+距离,左边格子最短+距离)

  • 注意最右边和最下面时只能朝一个方向走

  • 暴力递归不会记录子问题解，O(2ⁿ²)；记忆化搜索O(n²)；动态规划用数组记录子问题解，优化过程与状态转移方程有关，与原始题目相关性不大

    • 暴力递归的可变参数 = 动规数组几维表 - 解空间大小

    • 确定目标点；确定basecase（不依赖项）；

    • 本题的动规：先由最后点推出最下面行以及最右边行，然后依次往上确定次右与次下行。

• 算法实现（Java）

public static int minPath1(int[][] matrix) {	// 暴力递归
		return process1(matrix, matrix.length - 1, matrix[0].length - 1);	// 0,0位置到x,y位
	}

	public static int process1(int[][] matrix, int i, int j) {		//相当于从右下走到左上
		int res = matrix[i][j];
		if (i == 0 && j == 0) {		// 在左上点
			return res;
		}
		if (i == 0 && j != 0) {		// 在最左边，只能向上
			return res + process1(matrix, i, j - 1);
		}
		if (i != 0 && j == 0) {		// 在最上边，只能向左
			return res + process1(matrix, i - 1, j);
		}
		return res + Math.min(process1(matrix, i, j - 1), process1(matrix, i - 1, j));
	}

	public static int minPath2(int[][] m) {		// 动态规划
		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {	// 相当于每一步记录在了数组中，不会重复计算，之前计算过的直接索引即可
			return 0;
		}
		int row = m.length;
		int col = m[0].length;
		int[][] dp = new int[row][col];
		dp[0][0] = m[0][0];
		for (int i = 1; i < row; i++) {
			dp[i][0] = dp[i - 1][0] + m[i][0];
		}
		for (int j = 1; j < col; j++) {
			dp[0][j] = dp[0][j - 1] + m[0][j];
		}
		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
			}
		}
		return dp[row - 1][col - 1];
	}

	// for test
	public static int[][] generateRandomMatrix(int rowSize, int colSize) {
		if (rowSize < 0 || colSize < 0) {
			return null;
		}
		int[][] result = new int[rowSize][colSize];
		for (int i = 0; i != result.length; i++) {
			for (int j = 0; j != result[0].length; j++) {
				result[i][j] = (int) (Math.random() * 10);
			}
		}
		return result;
	}

	public static void main(String[] args) {
		int[][] m = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, { 8, 8, 4, 0 } };
		System.out.println(minPath1(m));
		System.out.println(minPath2(m));

		m = generateRandomMatrix(6, 7);
		System.out.println(minPath1(m));
		System.out.println(minPath2(m));
	}

题目八：数组中Σ是否相等所给数（背包问题）

• 题目表述：给予一个数组和一个数，判断是否能从数组中选取任意数之和与所给数相等。

• 思想：

  • 对于每一个数组元素，都有判断拿或者不拿，相当于一个状态，状态值就是拿了的数Σ，其中变化参数有两个，索引与Σ值，所以动规解空间大小就是二维表[n][aim]

  • eg. [3,2,7],aim=10。一开始状态a，对应值sum=0，索引i=0(相当于就是状态a)，状态转移b，看索引i=1，对应值sum=3/0(拿或者不拿)，循环重复。

  • 边界条件就是任意i，只要sum等于aim即True；最大i，sum!=aim即False - 所以仍是从数组[任意i,aim]往前面推是true还是false。

• 算法实现（Java）

public static boolean money1(int[] arr, int aim) {
		return process1(arr, 0, 0, aim);
	}

	public static boolean process1(int[] arr, int i, int sum, int aim) {	// (i,sum) i表示现在考虑数组下标i位置,sum表示目前选取数字Σ是sum,aim表示总目标
		if (sum == aim) {		// 边界条件	
			return true;
		}
		if (i == arr.length) {	// i=length，在最后元素后下标
			return false;
		}
		return process1(arr, i + 1, sum, aim) || process1(arr, i + 1, sum + arr[i], aim);	// 前不要a[i];后要a[i+1]
	}

	public static boolean money2(int[] arr, int aim) {			// 可变参数两个，所以创建二维表 - 一个存储i变化一个存储sum变化
		boolean[][] dp = new boolean[arr.length + 1][aim + 1];		
		for (int i = 0; i < dp.length; i++) {		// 边界条件就是所有aim位置都是true
			dp[i][aim] = true;
		}
		for (int i = arr.length - 1; i >= 0; i--) {
			for (int j = aim - 1; j >= 0; j--) {
				dp[i][j] = dp[i + 1][j];
				if (j + arr[i] <= aim) {
					dp[i][j] = dp[i][j] || dp[i + 1][j + arr[i]];	//前者不要i后者要i
				}
			}
		}
		return dp[0][0];	// [][]表示是否可达 0,0初始
	}

	public static void main(String[] args) {
		int[] arr = { 1, 4, 8 };
		int aim = 12;
		System.out.println(money1(arr, aim));
		System.out.println(money2(arr, aim));
	}

题目九：整数背包问题

• 题目表述：给定一个w[]和v[]，背包一定空间bag，装一组商品放背包，价值p[]，重量c[]，求能拿的最大价值。 - 商品整体不能细分。

• 思想：

  • 暴力递归跟上述一样，return的不是true/false而是价值，可变参数仍然是遍历i与重量cost

  • 动态规划跟上题类似，转为二维表，[][]表示可以添加的最大价值，从最后开始往前状态转移 - [bag]后都是int系统最小值(相当于负值)，而[i]值处都是0，相当于已经把物体都处理完成了，没有其他价值可以加进来了。 - 往前每遍历一个都在[][]赋值其价值，分为取跟不取。

  • 无后效性：能改成动态规划的重要性质，存在空间换时间的解，怎么到子状态的路径不影响子状态的返回值。eg. dp[3][3]可能有多种到此的情况，但是前面的不同路径并不影响dp[3][3]的返回值结果。

    1. 分析可变参数(解空间大小) - 需要得到的结果/值直接作为返回值而不是作为可变参

    2. 确定最终状态 - 要返回的状态

    3. 根据basecase确定初始状态 - 边界条件

    4. 确定普遍位置依赖的状态转移函数

• 算法实现（Java）

public static int maxValue1(int[] c, int[] p, int bag) { //递归
		return process1(c, p, 0, 0, bag);
	}

	public static int process1(int[] c, int[] p, int i, int cost, int bag) {		// i索引cost所带重量和，可变参数两个，解空间二维表
		if (cost > bag) {		// 剪枝 - 如果当前重量大于背包重量 
			return Integer.MIN_VALUE;
		}
		if (i == c.length) {	// 索引越界
			return 0;
		}
		return Math.max(process1(c, p, i + 1, cost, bag), p[i] + process1(c, p, i + 1, cost + c[i], bag));	// return的就是价值，所以不用算它为变参
	}

	public static int maxValue2(int[] c, int[] p, int bag) { //动规
		int[][] dp = new int[c.length + 1][bag + 1];	// bag最大空间，c.length最多放的东西个数
		for (int i = c.length - 1; i >= 0; i--) {	// 逐渐减小
			for (int j = bag; j >= 0; j--) {
				dp[i][j] = dp[i + 1][j];
				if (j + c[i] <= bag) {		// 边界条件就是越界或者bag超重
					dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
				}
			}
		}
		return dp[0][0];	// 存放的是从该位置起能放的最多东西
	}

	public static void main(String[] args) {
		int[] c = { 3, 2, 4, 7 };
		int[] p = { 5, 6, 3, 19 };
		int bag = 11;
		System.out.println(maxValue1(c, p, bag));
		System.out.println(maxValue2(c, p, bag));
	}

题目二：汉诺塔问题（从此到后都是练习递归）

• 题目表述：三个柱子，最左边有n个环，最上到最下从小到大环，称为n层汉诺塔；打印n层汉诺塔从最左移到最右的的全部过程。 - 小环只能移到大环上（环下面的其他环必须比自己小）

• 思路：

  • n层分解：n-1层从from->mid，第n层from->to。然后是n-1层从mid->to；

  • 最后一部n-1层从mid->to，相当于mid和from互换，形成了一个（n-1）汉诺塔的子问题

• 算法实现（Java）

public static void hanoi(int n) {
		if (n > 0) {
			func(n, "left", "mid", "right");
		}
	}

	public static void func(int n, String from, String mid, String to) {	//n表示环数
		if (n == 1) {
			System.out.println("move from " + from + " to " + to);
		} else {
			func(n - 1, from, to, mid);	// 前n-1,from—>mid
			func(1, from, mid, to);		// 第n,from->to //剩一个环
			func(n - 1, mid, from, to);	// 前n-1,mid->to	//相当于mid和from互换了
		}
	}

	public static void main(String[] args) {
		int n = 3;
		hanoi(n);
	}

题目三：打印一个字符串的全部子序列

• 题目表述：打印一个字符串的全部子序列，包括空字符串。

• 思路：

  • 跟之前的递归动规的题目一样，都是对于每个子元素要或不要的子问题。

  • 由于每一步都需要打印，故不用对递归转变成动规。

  • 算法实现（java）

public static void printAllSubsquence(String str) {	// 如果只是单纯打印，那每个形成的序列都要打印，所以不用改成动规
		char[] chs = str.toCharArray();
		process(chs, 0);
	}

	public static void process(char[] chs, int i) {	// char[]就是所有包含字符，i索引
		if (i == chs.length) {
			System.out.println(String.valueOf(chs));    // 过了最后位置，打印
			return;
		}
		process(chs, i + 1);	// 递归，不要
		char tmp = chs[i];
		chs[i] = 0;
		process(chs, i + 1);	// 递归，要
		chs[i] = tmp;
	}

	public static void main(String[] args) {
		String test = "abc";
		printAllSubsquence(test);
	}

题目四：打印一个字符串的全排列（要求出现/不出现重复字符串）

• 题目表述：打印一个字符串的全排列。 - （进阶：打印一个字符串的全排列，要求不要出现重复字符串）

• 思路：

  • ① 跟之前的拿或不拿的递归不太一样，这次是(每个字符开头，和剩下字符全排列组合)的递归 - 也符合最优子结构问题

  • 如何实现：固定i位置为头元素，从头元素开始遍历[j]，与后续的每个j位置都进行交换一次，递归调用除头元素外的序列（i++），再把i与j交换回来，这样递归到i=length打印，便实现了全排列的递归。

  • ② 不出现重复字符串只需要建立一个hashset即可。

  • 算法实现（java）

public static void printAllPermutations1(String str) {	// 有重复项的全排列打印
		char[] chs = str.toCharArray();
		process1(chs, 0);
	}

	public static void process1(char[] chs, int i) {
		if (i == chs.length) {
			System.out.println(String.valueOf(chs));	// 过了最后位置，打印
		}
		for (int j = i; j < chs.length; j++) {		// 跟后续每个位置进行遍历交换
			swap(chs, i, j);
			process1(chs, i + 1);
			swap(chs, i, j);	// 再交换回来
		}
	}

	public static void printAllPermutations2(String str) {
		char[] chs = str.toCharArray();
		process2(chs, 0);
	}

	public static void process2(char[] chs, int i) {	
		if (i == chs.length) {
			System.out.println(String.valueOf(chs));
		}
		HashSet<Character> set = new HashSet<>();
		for (int j = i; j < chs.length; j++) {		// 每个换的字符和选的字符不重复即可
			if (!set.contains(chs[j])) {	
				set.add(chs[j]);
				swap(chs, i, j);
				process2(chs, i + 1);
				swap(chs, i, j);
			}
		}
	}

	public static void swap(char[] chs, int i, int j) {
		char tmp = chs[i];
		chs[i] = chs[j];
		chs[j] = tmp;
	}

	public static void main(String[] args) {
		String test1 = "abc";
		printAllPermutations1(test1);
		System.out.println("======");
		printAllPermutations2(test1);
		System.out.println("======");

		String test2 = "acc";
		printAllPermutations1(test2);
		System.out.println("======");
		printAllPermutations2(test2);
		System.out.println("======");
	}

题目五：母牛数量问题

• 题目表述：母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。求N年后，母牛的数量。（进阶：如果每头牛只能活10年）

• 思路：

  • 最优解使用矩阵乘法可以达到O(logN)，这里只说递归做法（一切符合该通项的解都可以用logN时间复杂度，斐波拉契数列矩阵乘法）
  • 递归：数列递归表达式：F(n) = F(n-1) + F(n-3)，去年牛+可以生小牛的牛
  • 不用递归：用三个变量来存储去年前年大前年的数量，遍历n-4得到n年后母牛的数量。 - 顺序计算O(n)
  • 进阶：F(n) = F(n-1) + F(n-3) - F(n-10)即可
  • 算法实现（java）：

// 假设不会死
	public static int cowNumber1(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2 || n == 3) {
			return n;
		}
		return cowNumber1(n - 1) + cowNumber1(n - 3);
	}

	public static int cowNumber2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2 || n == 3) {
			return n;
		}
		int res = 3;
		int pre = 2;
		int prepre = 1;
		int tmp1 = 0;
		int tmp2 = 0;
		for (int i = 4; i <= n; i++) {
			tmp1 = res;
			tmp2 = pre;
			res = res + prepre;
			pre = tmp1;
			prepre = tmp2;
		}
		return res;
	}

	public static void main(String[] args) {
		int n = 20;
		System.out.println(cowNumber1(n));
		System.out.println(cowNumber2(n));
	}

题目六：只使用递归实现逆序栈

• 题目表述：给予一个栈，返回逆序栈，要求不使用其他额外数据结构，只使用递归函数实现。

• 思路：

  • ① getAndRemoveLastElement( )：得到并弹出栈底元素，并且使栈内其他元素保持原有顺序留在栈内

    • 先result记录pop()栈顶元素，如果为空则返回；非空则递归调用getAndRemoveLastElement得到返回值last，把之前的栈顶元素压栈，返回last。
    • 所以返回的一定是栈底元素，并且是通过递归一步一步传上来的，每一步递归都把栈顶元素拿出来再压回去。

  • ② reverse( )：使栈逆序的函数

    • 先判空，空则返回；调用getAndRemoveLastElement得到栈底元素记录为i并且使栈内其他元素保持原有顺序留在栈内
    • 然后再调用自己reverse( )，调用最底层栈空，并且从外到内层记录的元素为从底到顶；之后把i压栈，则根据递归就是把最开始的栈顶元素压栈直到栈底元素压栈，这样就实现了栈的逆序。

  • 算法实现（java）

public static void reverse(Stack<Integer> stack) {
		if (stack.isEmpty()) {
			return;
		}
		int i = getAndRemoveLastElement(stack);
		reverse(stack);
		stack.push(i);
	}

	public static int getAndRemoveLastElement(Stack<Integer> stack) {
		int result = stack.pop();
		if (stack.isEmpty()) {
			return result;
		} else {
			int last = getAndRemoveLastElement(stack);
			stack.push(result);
			return last;
		}
	}

	public static void main(String[] args) {
		Stack<Integer> test = new Stack<Integer>();
		test.push(1);
		test.push(2);
		test.push(3);
		test.push(4);
		test.push(5);
		reverse(test);
		while (!test.isEmpty()) {
			System.out.println(test.pop());
		}

	}