-
动态规划基础入门【1】
动态规划基础入门
1 基础概念
2 经典题目
诀窍：常规递归 -> 缓存表 -> 动态规划
需要有一个尝试的过程2.1 机器人走的方法数
假设有排成一行的N个位置，记为1~N，N>=2
开始时，机器人在其中的M位置上（M一定是1~N中的一个）
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数。2.1.1 基础写法（普通递归）
普通递归方式，但是会有太多重复值计算；类比斐波那契,f(6) = f(5) + f(4), f(5) = f(4) + f(3)
/** * 普通递归方式【缺点：有太多重复值计算】 */ public class RobotWalkDemo { /** * @param N 一共有多少个位置 * @param start 机器人起始位置 * @param aim 机器人目标位置 * @param K 一共可以走几步 * @return */ 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); } /** * @param cur 机器人当前位置 * @param rest 剩余步数 * @param aim 目标位置 * @param N 一共有多少位置【1~N】 * @return 机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？ */ public static int process1(int cur, int rest, int aim, int N) { if (rest == 0) { //没有步数了，看看是否走到了目标位置 return cur == aim ? 1 : 0; } //机器人在1位置，只能往右走 if (cur == 1) { return process1(cur + 1, rest - 1, aim, N); } //机器人在最后位置N，只能往左走 if (cur == N) { return process1(cur - 1, rest - 1, aim, N); } //机器人在中间，可以往两边走，结果为左右数之和 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
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
2.1.2 使用缓存表
将每次结果都放在一个dp缓存表中，如果缓存中有数据直接从缓存表拿
/** * 利用缓存表【记忆化搜索】 * * @param N * @param start * @param aim * @param K * @return */ 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; } //利用缓存表【dp】:K+1是因为0步也算一种情况 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 -> process2(cur, rest) 之前没算过 //dp[cur][rest] != -1 -> process2(cur, rest) 之前算过 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(cur + 1, rest - 1, aim, N, dp); } else if (cur == N) { ans = process2(cur - 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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
2.1.3 动态规划
/** * 利用标准动态规划求解 * * @param N 位置个数 * @param start 起始位置 * @param aim 目标位置 * @param K 步数 * @return */ 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]; //base case dp[aim][0] = 1; for (int rest = 1; rest <= K; rest++) { //当cur为第一个位置时候 dp[1][rest] = dp[2][rest - 1]; for (int cur = 2; cur < N; cur++) { //cur为中间位置 dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1]; } //当cur为最后一个位置时 dp[N][rest] = dp[N - 1][rest - 1]; } return dp[start][K]; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
2.2 先手后手纸牌游戏
给定一个整型数组arr，代表数值不同的纸牌排成一条线
玩家A和玩家B依次拿走每张纸牌
规定玩家A先拿（先手）， 玩家B后拿（后手）
但是每个玩家每次只能拿走最左或最右的纸牌
玩家A和玩家B都绝顶聪明【会考虑下一次让对方拿到最小的】
请返回最后获胜者的分数。2.2.1 常规递归求解
按照常规思路尝试即可
/** * 常规递归方法求解 */ public class CardsInLine { public static int win1(int[] arr) { if (arr == null || arr.length == 0) { return 0; } //先手获得的分数 int first = f1(arr, 0, arr.length - 1); //后手获得的分数 int second = g1(arr, 0, arr.length - 1); return Math.max(first, second); } //先手 public static int f1(int[] arr, int L, int R) { if (L == R) { //只剩一张牌了，先手直接拿到 return arr[0]; } //第一种情况：先手拿左手边的牌【左手牌的值+下一次自己作为后手时拿的值】 int p1 = arr[L] + g1(arr, L + 1, R); //第二种情况：先拿右手边的牌【右手边的牌+下一次作为后手时拿的最大值】 int p2 = arr[R] + g1(arr, L, R - 1); //我肯定选择获得分数最大的走法 return Math.max(p1, p2); } //后手 public static int g1(int[] arr, int L, int R) { if (L == R) { //只剩一张牌了，牌肯定被先手拿走 return 0; } //第一种情况：对手拿的左手边的值 int p1 = f1(arr, L + 1, R); //第二种情况：对手拿的自己右手边的值 int p2 = f1(arr, L, R - 1); //我作为第一局的后手，肯定只有获得两种情况的最小值【对手会想尽办法让我获得最小值】 return Math.min(p1, p2); } public static void main(String[] args) { int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 }; System.out.println(win1(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
2.2.2 缓存表方式
两张缓存表fmap、gmap，fmap[L][R]其值代表当数组的左边界为L时，右边界为R时的值
/** * 使用缓存表【两张】 * @param arr * @return */ public static int win2(int[] arr){ if(arr == null || arr.length == 0){ return 0; } int N = arr.length; int[][] fmap = new int[N][N]; int[][] gmap = new int[N][N]; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ fmap[i][j] = -1; gmap[i][j] = -1; } } int first = f2(arr, 0, arr.length - 1, fmap, gmap); int second = g2(arr, 0, arr.length - 1, fmap, gmap); return Math.max(first, second); } public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap){ if(fmap[L][R] != -1){ return fmap[L][R]; } int ans = 0; if(L == R){ //先手直接获得 ans = arr[L]; } else { //情况一：拿的左边的牌 int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap); //情况二：拿的右边的牌 int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap); ans = Math.max(p1, p2); } fmap[L][R] = ans; return ans; } public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap){ if(gmap[L][R] != -1){ return gmap[L][R]; } int ans = 0; if(L != R){ //情况一：对手拿走了左边的牌 int p1 = f2(arr, L+1, R, fmap, gmap); //情况二：对手拿走了右边的牌 int p2 = f2(arr, L, R - 1, fmap, gmap); ans = Math.min(p1, p2); } gmap[L][R] = ans; return ans; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
2.2.3 动态规划
/** * 动态规划求解 * @param arr * @return */ public static int win3(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int N = arr.length; int[][] fmap = new int[N][N]; int[][] gmap = new int[N][N]; for (int i = 0; i < N; i++) { //L == R 情况 fmap[i][i] = arr[i]; } for (int startCol = 1; startCol < N; startCol++) { int L = 0;//row int R = startCol;//col //行不会越界，是列提前越界 while (R < N) { //先手 fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]); //后手 gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]); L++; R++; } } return Math.max(fmap[0][N - 1], gmap[0][N - 1]); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
2.3 包中最大价值（背包问题）
给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
动态规划解法：由尝试 -> 动态规划
2.3.1 尝试
//背包问题：返回包得到的最大价值 public class KnapsackDemo { /** * 假设w、v数组中没有负数 * * @param w 物品重量 * @param v 物品对应价值 * @param bag 包的容量 * @return */ public static int maxValue(int[] w, int[] v, int bag) { if (w == null || v == null || w.length != v.length || w.length == 0) { return 0; } //尝试函数 return process(w, v, 0, bag); } //index 0 ~ N //rest 负数 ~ bag【包的剩余容量】 public static int process(int[] w, int[] v, int index, int rest){ if(rest < 0){ //rest小于零，表明之前的尝试是错误的 return -1; } if(index == w.length){ return 0; } //没有要index位置的货物 int p1 = process(w, v, index + 1, rest); int p2 = 0; int next = process(w, v, index + 1, rest - w[index]); if(next != -1){ //该尝试可行 //要了index位置的货物 p2 = v[index] + next; } return Math.max(p1, p2); } public static void main(String[] args) { int[] weights = { 3, 2, 4, 7, 3, 1, 7 }; int[] values = { 5, 6, 3, 19, 12, 4, 2 }; int bag = 15; System.out.println(maxValue(weights, values, bag));//42 // System.out.println(dp(weights, values, bag)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
2.3.2 dp方法
由尝试改为动态规划：递归改为从数组中拿值
/** * 动态规划实现 * @param w * @param v * @param bag * @return */ public static int dp(int[] w, int[] v, int bag){ //条件判断不变【照抄"尝试"】 if(w == null || v == null || w.length != v.length || w.length == 0){ return 0; } int N = w.length; int[][] dp = new int[N+1][bag+1]; for(int index = N - 1; index >= 0; index--){ //依赖index+1位置，由下往上推 for(int rest = 0; rest <= bag; rest++){ //process(w, v, index + 1, rest); //process(w, v, index + 1, rest - w[index]); //同一行的数据相互是不依赖的，因此可以从左往右填，也可以从右往左填 int p1 = dp[index+1][rest]; int p2 = 0; int next = rest - w[index] < 0 ? -1 : dp[index+1][rest - w[index]]; if(next != -1){ p2 = v[index] + next; } dp[index][rest] = Math.max(p1, p2); } } return dp[0][bag]; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
2.4 数字-字符串转换
规定1和A对应、2和B对应、3和C对应…26和Z对应，那么一个数字字符串比如"111”就可以转化为:“AAA”、“KA"和"AK”，给定一个只有数字字符组成的字符串str，返回有多少种转化结果
2.4.1 尝试
//数字转字符串【转法】 //str只含数字0~9 public static int number(String str) { if (str == null || str.length() == 0) { return 0; } return process(str.toCharArray(), 0); } //str[0..i-1]转化无需过问 //str[i...]去转化，返回有多少种转化方案 public static int process(char[] str, int i) { if (i == str.length) { return 1; } //i没走到最后，说明还有数字剩余 if (str[i] == '0') { //之前的决定有问题[1~26：没有单独的0] return 0; } //str[i] != '0' //可能性1：单转 int ways = process(str, i + 1); //可能性2：合并转【11 -> K】 if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) { ways += process(str, i + 2); } return ways; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
2.4.1 递归（一维数组）
//从右往左的动态规划 //dp[i]:str[i..]有多少种转化方式 public static int dp1(String s){ if(s == null || s.length() == 0){ return 0; } char[] str = s.toCharArray(); int N = str.length; int[] dp = new int[N+1]; dp[N] = 1; for(int i = N - 1; i >= 0; i--){ if(str[i] != '0'){ int ways = dp[i+1]; if(i + 1 < str.length && (str[i] - '0') * 10 + str[i+1] - '0' < 27){ ways += dp[i+2]; } dp[i] = ways; } } return dp[0]; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
2.5 贴纸拼接字符串(LeetCode - 691. 贴纸拼词)
给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文，arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来，返回需要至少多少张贴纸可以完成这个任务。
例子：str= “babac”，arr = {“ba”,“c”,“abcd”}ba + ba + c 3
abcd + abcd 2 abcd+ba 2所以返回2(最少)
2.5.1 尝试
//返回最少所用贴纸数 public static int minStickers(String[] stickers, String target) { int ans = process1(stickers, target); //如果返回最大值，表明没有结果 return ans == Integer.MAX_VALUE ? -1 : ans; } /** * @param stickers 贴纸数组 * @param target 目标字符串 * @return 最少张数 */ public static int process1(String[] stickers, String target) { if (target.length() == 0) { return 0; } int min = Integer.MAX_VALUE; //每一张作为第一张尝试 for (String first : stickers) { //first能够消除掉多少target里面的字符 String rest = minus(target, first); if (rest.length() != target.length()) { min = Math.min(min, process1(stickers, rest)); } } //如果min不是最大值表明有效【+1加上本身】 return min + (min == Integer.MAX_VALUE ? 0 : 1); } public static String minus(String s1, String s2) { char[] str1 = s1.toCharArray(); char[] str2 = s2.toCharArray(); int[] count = new int[26]; for (char cha : str1) { count[cha - 'a']++; } for (char cha : str2) { count[cha - 'a']--; } StringBuilder stb = new StringBuilder(); for (int i = 0; i < 26; i++) { if (count[i] > 0) { for (int j = 0; j < count[i]; j++) { stb.append((char) (i + 'a')); } } } return stb.toString(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
2.5.2 减枝+贪心
//减枝 public static int minStickers2(String[] stickers, String target){ int N = stickers.length; //关键优化（用词频表替代贴纸数组） int[][] counts = new int[N][26]; for(int i = 0; i < N; i++){ char[] str = stickers[i].toCharArray(); for(char cha : str){ counts[i][cha - 'a']++; } } int ans = process2(counts, target); return ans == Integer.MAX_VALUE ? -1 : ans; } /** * * @param stickers 贴纸词频数组 * @param t 目标字符串 * @return */ public static int process2(int[][] stickers, String t){ if(t.length() == 0){ return 0; } //target做出词频统计 char[] target = t.toCharArray(); int[] tcounts = new int[26]; for(char cha : target){ tcounts[cha - 'a']++; } int N = stickers.length; int min = Integer.MAX_VALUE; for(int i = 0; i < N; i++){ //尝试第一张贴纸是谁 int[] sticker = stickers[i]; //最关键的优化（最重要的剪枝，这一步也是贪心） if(sticker[target[0] - 'a'] > 0){ StringBuilder stb = new StringBuilder(); for(int j = 0; j < 26; j++){ if(tcounts[j] > 0){ int nums = tcounts[j] - sticker[j]; for(int k = 0; k < nums; k++){ stb.append((char)(j+'a')); } } } String rest = stb.toString(); min = Math.min(min, process2(stickers, rest)); } } return min + (min == Integer.MAX_VALUE ? 0 : 1); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
2.5.3 dp（缓存表）
//方法三：加缓存表【dp，记忆化搜索】 public static int minStickers3(String[] stickers, String target){ int N = stickers.length; int[][] counts = new int[N][26]; for(int i = 0; i < N; i++){ char[] str = stickers[i].toCharArray(); for(char cha : str){ counts[i][cha - 'a']++; } } HashMap<String, Integer> dp = new HashMap<>(); dp.put("", 0); int ans = process3(counts, target, dp); return ans == Integer.MAX_VALUE ? -1 : ans; } public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp){ if(dp.containsKey(t)){ return dp.get(t); } char[] target = t.toCharArray(); int[] tcounts = new int[26]; for(char cha : target){ tcounts[cha - 'a']++; } int N = stickers.length; int min = Integer.MAX_VALUE; for(int i = 0; i < N; i++){ int[] sticker = stickers[i]; if(sticker[target[0] - 'a'] > 0){ StringBuilder stb = new StringBuilder(); for(int j = 0; j < 26; j++){ if(tcounts[j] > 0){ int nums = tcounts[j] - sticker[j]; for(int k = 0; k < nums; k++){ stb.append((char) (j+'a')); } } } String rest = stb.toString(); min = Math.min(min, process3(stickers, rest, dp)); } } int ans = min + (min == Integer.MAX_VALUE ? 0 : 1); dp.put(t, ans); return ans; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
-
相关阅读:
矢量场的旋度和散度
力扣：122.买卖股票的最佳时机II
动态规划模型：0-1背包问题
UITableView的style是UITableViewStyleGrouped
Vue基础语法的进阶，事件处理器，自定义组件及组件通信
Deno 下一代JavaScript运行时
用于机器学习的 NumPy（ML）
一、Rabbit的介绍与安装
神经网络的发展历史
几分钟让你了解Linux下文件权限掩码及作用
- 原文地址：https://blog.csdn.net/weixin_45565886/article/details/126686349
