前言

动态规划的目的就是避免重复计算，在暴力递归的过程中若在计算过程中产生了重复计算那么就可以进行动态规划的优化。以空间换时间，可以根据暴力递归的过程写出动态规划的过程。

一、背包问题

题目：

public class BagProblem {public static int solution(int[] weights, int[] values, int bag) {int[][] dp = new int[weights.length + 1][bag + 1];for(int i=weights.length - 1; i>=0; --i) {for(int j=1; j<=bag; ++j) {dp[i][j] = dp[i + 1][j];if(j >= weights[i]) {dp[i][j] = Math.max(dp[i][j], values[i] + dp[i+1][j-weights[i]]);}}}return dp[0][bag];}public static void main(String[] args) {System.out.println(solution(new int[] {20, 30, 100}, new int[] {40, 50, 80}, 100));}}

运行结果：

二、字符串转化问题

题目：

package DynamicProgramming;public class TransString {public static int solution(String str) {int len = str.length();int[] dp = new int[len + 1];dp[len] = 1;for(int i=len-1; i>=0; --i) {if(str.charAt(i) == '0') {dp[i] = 0;}else if(str.charAt(i) == '1') {dp[i] = dp[i + 1];if(i != len - 1) {dp[i] += dp[i + 2];}}else if(str.charAt(i) == '2') {dp[i] = dp[i + 1];if(i != len - 1 && str.charAt(i) >= '0' && str.charAt(i) <= '6') {dp[i] += dp[i + 2];}}else {dp[i] = dp[i + 1];}}return dp[0];}public static void main(String[] args) {System.out.println(solution("1111"));}}

运行结果

三、纸牌问题

题目：

package DynamicProgramming;import java.util.Arrays;public class PaperCardScore {public static String solution(int[] card) {int n = card.length;int[][] first = new int[n][n];	//先手矩阵int[][] second = new int[n][n];	//后手矩阵for(int i=0; i<n; i++) {first[i][i] = card[i];	//只剩下一张牌，先手会取走这张 后手为0}//r为剩余牌的数量for(int r=2; r<=n; r++) {// 枚举范围for(int i=0;i<n - r + 1;++i) {int j = i + r - 1;first[i][j] = Math.max(card[i] + second[i+1][j], card[j] + second[i][j - 1]);	// 取左边牌和右边牌 看那边大second[i][j] = Math.min(first[i + 1][j], first[i][j - 1]);						// 假如先手取左边 假如先手取右边 后手被动只能要小的}}String ret = "先手分数为:" + first[0][n - 1] + " 后手分数为:" + second[0][n - 1];if(first[0][n - 1] > second[0][n - 1]) {ret = "先手胜利! " + ret;}else if(first[0][n - 1] < second[0][n - 1]) {ret = "后手胜利! " + ret;}else {ret = "平局! " + ret;}return ret;}public static void main(String[] args) {int[][] cards = new int[][] {{1, 100, 20, 30 , 2},{1, 300, 2},{1, 300, 500},{300, 300},{20, 25, 85, 42, 8},{1, 2, 3, 4 ,5, 42}};for(int i=0; i<cards.length; ++i) {System.out.println("---------" + Arrays.toString(cards[i]) + "---------");System.out.println(solution(cards[i]));System.out.println();}}
}

运行结果

四、最少贴纸数

题目

思路: 记忆化搜索

package DynamicProgramming;import java.util.HashMap;public class lestStickNum {public static int solution(String str, String[] stick) {int m = stick.length;int[][] map = new int[m][26];	// 构造贴纸mapfor(int i=0; i<m; ++i) {int len = stick[i].length();for(int j=0; j<len; ++j) {map[i][stick[i].charAt(j) - 'a'] += 1;}}HashMap<String, Integer> dp = new HashMap<>();	// 存储记忆dp.put("", 0);					// 空字符串用0张return helper(map, str, dp);}public static int helper(int[][] map, String rest, HashMap<String, Integer> dp) {if(dp.containsKey(rest)) {return dp.get(rest);}int len = rest.length();int[] temp = new int[26];for(int i=0; i<len; ++i) {temp[rest.charAt(i) - 'a']++;}int ans = Integer.MAX_VALUE;for(int i=0; i<map.length; ++i) {if(map[i][rest.charAt(0) - 'a'] == 0) {	// 必须有字符匹配，这里匹配第一个continue;}int[] newRest = new int[26];StringBuilder sb = new StringBuilder();for(int j=0; j<26; ++j) {newRest[j] = temp[j] - map[i][j] >= 0? temp[j] - map[i][j] :0;for(int k=0; k<newRest[j]; k++) {sb.append((char)('a' + j));}}int next = helper(map, sb.toString(), dp);		// 匹配剩余字符串最少几张贴纸if(next != -1) {ans = ans > next + 1? next + 1: ans;}}if(ans == Integer.MAX_VALUE) ans = -1;	// -1表示无法匹配dp.put(rest, ans);return ans;}public static void main(String[] args) {System.out.println(solution("aabbccdd", new String[] {"a", "b", "c", "d"}));System.out.println(solution("aabbccdd", new String[] {"ab", "b", "c", "d"}));System.out.println(solution("aabbccdd", new String[] {"abc", "b", "c", "d"}));System.out.println(solution("aabbccdd", new String[] {"abdc", "b", "c", "d"}));System.out.println(solution("aabbccdd", new String[] {"abc", "b", "c"}));}
}