栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

从暴力递归到动态规划

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

从暴力递归到动态规划

主要是参考【左程云】和【代码随想录】的讲解,两者都有更丰富的题解可供入门后练习
 

01 从暴力递归到动态规划(机器人步行问题)

参考:

  • 左程云动态规划的讲解:https://www.bilibili.com/video/BV1ET4y1U7T6
  • 笔记:https://github.com/algorithmzuo/class-notes/blob/main/课堂内容汇总/算法和数据结构体系学习班
  • 代码:https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src

假设有排成一行的N个位置记为1~N,N一定大于或等于2
开始时机器人在其中的M位置上(M一定是1~N中的一个)

  • 如果机器人来到1位置,那么下一步只能往右来到2位置;
  • 如果机器人来到N位置,那么下一步只能往左来到N-1位置;
  • 如果机器人来到中间位置,那么下一步可以往左走或者往右走;

规定机器人必须走K步,最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P,返回方法数量

1.1 暴力递归

思路:

  • 如果机器人来到1位置,那么下一步只能往右来到2位置(下一步cur=2,并且rest-1);
  • 如果机器人来到N位置,那么下一步只能往左来到N-1位置(下一步cur=2,并且rest-1);
  • 如果机器人再其他位置,那么下一步可以往左走或者往右走(下一步有两种选择:①向左走: cur=cur-1,并且rest-1;②向右走: cur=cur+1,并且rest-1);
public class Code01_RobotWalk {

	public static int ways1(int N, int start, int aim, int K) {
		if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
			return -1;
		}
		return process1(start, K, aim, N);
	}

	// 机器人当前来到的位置是cur,
	// 机器人还有rest步需要去走,
	// 最终的目标是aim,
	// 有哪些位置?1~N
	// 返回:机器人从cur出发,走过rest步之后,最终停在aim的方法数,是多少?
	public static int process1(int cur, int rest, int aim, int N) {
		if (rest == 0) { // 如果已经不需要走了,走完了!
			return cur == aim ? 1 : 0;
		}
		// (cur, rest)
		if (cur == 1) { // 1 -> 2
			return process1(2, rest - 1, aim, N);
		}
		// (cur, rest)
		if (cur == N) { // N-1 <- N
			return process1(N - 1, rest - 1, aim, N);
		}
		// (cur, rest)
		return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
	}

	
	public static void main(String[] args) {
		System.out.println(ways1(5, 2, 4, 6));
	}

}
1.2 缓存

思路:

  • 递归的过程会有重复计算的问题
  • 所以建立一个缓存表dp[][],如果结果在dp里有,就直接取出,否则递归
public class Code01_RobotWalk {

	public static int ways2(int N, int start, int aim, int K) {
		if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
			return -1;
		}
		int[][] dp = new int[N + 1][K + 1];
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= K; j++) {
				dp[i][j] = -1;
			}
		}
		// dp就是缓存表
		// dp[cur][rest] == -1 -> process1(cur, rest)之前没算过!
		// dp[cur][rest] != -1 -> process1(cur, rest)之前算过!返回值,dp[cur][rest]
		// N+1 * K+1
		return process2(start, K, aim, N, dp);
	}

	// cur 范: 1 ~ N
	// rest 范:0 ~ K
	public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
		if (dp[cur][rest] != -1) {
			return dp[cur][rest];
		}
		// 之前没算过!
		int ans = 0;
		if (rest == 0) {
			ans = cur == aim ? 1 : 0;
		} else if (cur == 1) {
			ans = process2(2, rest - 1, aim, N, dp);
		} else if (cur == N) {
			ans = process2(N - 1, rest - 1, aim, N, dp);
		} else {
			ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
		}
		dp[cur][rest] = ans;
		return ans;

	}

	public static void main(String[] args) {
		System.out.println(ways2(5, 2, 4, 6));
	}

}
1.3 动态规划

思路:

  • dp[][]可以不通过递归获得,而是找到建立表格的规律,通过for循环填满这个表格
  • dp[cur][rest],如下图:
    • 第一列根据aim确定为0还是为1
    • 后面的每一列
      • 第一行cur=1,下一步是cur=2且rest-1,即第一行等于上一列的第二行dp[1][rest] = dp[2][rest - 1];
      • 最后一行cur=N,下一步是cur=N-1且rest-1,即最后一行等于上一列的倒数第二行dp[N][rest] = dp[N - 1][rest - 1];
      • 中间的行cur=x,下一步是cur=x+1也可以是cur=x-1,即上一列的 上一行和下一行 相加dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1]

public class Code01_RobotWalk {

	public static int ways3(int N, int start, int aim, int K) {
		if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
			return -1;
		}
		int[][] dp = new int[N + 1][K + 1];
		dp[aim][0] = 1;
		for (int rest = 1; rest <= K; rest++) {
			dp[1][rest] = dp[2][rest - 1];
			for (int cur = 2; cur < N; cur++) {
				dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
			}
			dp[N][rest] = dp[N - 1][rest - 1];
		}
		return dp[start][K];
	}

	public static void main(String[] args) {
		System.out.println(ways1(5, 2, 4, 6));
		System.out.println(ways2(5, 2, 4, 6));
		System.out.println(ways3(5, 2, 4, 6));
	}

}
02 背包问题

背包问题感觉参考【代码随想录】的讲解更清楚一点

  • 二维dp数组-视频:https://www.bilibili.com/video/BV1cg411g7Y6?vd_source=3a1ad336af3eaae4fcced56c75d309d1

  • 一维dp数组-视频:https://www.bilibili.com/video/BV1BU4y177kY/?spm_id_from=pageDriver&vd_source=3a1ad336af3eaae4fcced56c75d309d1

  • 讲解:https://programmercarl.com/背包理论基础01背包-1.html#_01-背包


主要的流程就是:

  1. dp数组含义
  2. 递推公式
  3. 初始化
  4. 遍历顺序

可能会遇到的面试题:
 
要求先实现一个纯二维的01背包
然后再问为什么两个for循环的嵌套顺序这么写? 反过来写行不行?(可以)
再讲一讲初始化的逻辑。
 
然后要求实现一个一维数组的01背包
一维数组的01背包,两个for循环的顺序反过来写行不行?为什么?(不可以,因为这是一个压缩后的,所以必须先遍历物品,再遍历背包)
为什么要倒序遍历?(保证物品只放入一次)

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/980929.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号