040、动态规划基本技巧（labuladong）

动态规划基本技巧

一、动态规划解题套路框架

基于labuladong的算法网站，动态规划解题套路框架；

1、基本介绍

基本套路框架：

• 动态规划问题的一般形式是求最值；
• 核心如下：
  • 穷举；
  • 明确base case；
  • 明确状态和状态转移，什么选择导致状态如何变化’
  • 定义dp数组，存储的值是什么

代码框架：

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):for 选择 in 所有可能的选择:# 此时的状态已经因为做了选择而改变result = 求最值(result, dp(状态1, 状态2, ...))return result# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：for 状态2 in 状态2的所有取值：for ...dp[状态1][状态2][...] = 求最值(选择1，选择2...)

2、斐波那契数列

力扣第509题，斐波那契数；

[509]斐波那契数//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int fib(int n) {// 判断 nif (n <= 1) {return n;}return dp(n);}// 动态规划int dp(int n) {int[] memo = new int[n + 1];// base casememo[0] = 0;memo[1] = 1;for (int i = 2; i <= n; i++) {memo[i] = memo[i - 1] + memo[i - 2];}return memo[n];}
}
//leetcode submit region end(Prohibit modification and deletion)

3、凑零钱问题

力扣第322题，零钱兑换；

[322]零钱兑换//leetcode submit region begin(Prohibit modification and deletion)
class Solution {/*** @param coins：不同面额的硬币数组* @param amount：需要凑满的总金额* @return 返回利用不同面额的硬币数组，凑满总金额时，最少的硬币个数*/public int coinChange(int[] coins, int amount) {// 利用一个备忘录数组memo = new int[amount + 1];// 将备忘录中填充值Arrays.fill(memo, -666);return find(coins, amount);}int[] memo;// 所需硬币个数int find(int[] coins, int amount) {// base caseif (amount == 0) {return 0;}if (amount < 0) {return -1;}// 防止重复计算if (memo[amount] != -666) {return memo[amount];}// 遍历 coins 数组int res = Integer.MAX_VALUE;for (int coin : coins) {// 如果此时选择 coin 这枚硬币，可以将问题分解成子问题int subRes = find(coins, amount - coin);// 比较结果if (subRes == -1) {continue;// 该情况无解}res = Math.min(res, subRes + 1);}// 将结果存入备忘录memo[amount] = res == Integer.MAX_VALUE ? -1 : res;return memo[amount];}
}
//leetcode submit region end(Prohibit modification and deletion)

二、动态规划设计：最长递增子序列

基于labuladong的算法网站，动态规划设计：最长递增子序列；

1、最长递增子序列

力扣第300题，最长递增子序列；

[300]最长递增子序列//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int lengthOfLIS(int[] nums) {// 利用一个备忘录int length = nums.length;// memo[i]：为i位置为结尾的最长严格递增子序列的长度int[] memo = new int[length];// 数组初始化Arrays.fill(memo, 1);int res = 0;// 开始遍历for (int i = 0; i < length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {memo[i] = Math.max(memo[i], 1 + memo[j]);}}}// 找到最大的for (int i = 0; i < length; i++) {if (memo[i] > res) {res = memo[i];}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)

2、俄罗斯套娃信封问题

力扣第354题，俄罗斯套娃信封问题；

[354]俄罗斯套娃信封问题//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// envelopes = [[w, h], [w, h]...]public int maxEnvelopes(int[][] envelopes) {int n = envelopes.length;// 按宽度升序排列，如果宽度一样，则按高度降序排列Arrays.sort(envelopes, new Comparator<int[]>(){public int compare(int[] a, int[] b) {return a[0] == b[0] ?b[1] - a[1] : a[0] - b[0];}});// 对高度数组寻找 LISint[] height = new int[n];for (int i = 0; i < n; i++)height[i] = envelopes[i][1];return lengthOfLIS(height);}public int lengthOfLIS(int[] nums) {// 利用一个备忘录int length = nums.length;// memo[i]：为i位置为结尾的最长严格递增子序列的长度int[] memo = new int[length];// 数组初始化Arrays.fill(memo, 1);int res = 0;// 开始遍历for (int i = 0; i < length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {memo[i] = Math.max(memo[i], 1 + memo[j]);}}}// 找到最大的for (int i = 0; i < length; i++) {if (memo[i] > res) {res = memo[i];}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)

三、最优子结构原理和 DP 数组遍历方向

基于labuladong的算法网站，最优子结构原理和 DP 数组遍历方向；

1、最优子结构

动态规划问题一般都是求最值问题，本质是重叠的子问题，从base case开始去往后推导，整个过程就是状态转移正确的过程；

2、如何一眼看出重叠子问题

最简单直接的办法是画出递归图，如果有重叠的子问题，就需要引入备忘录；

3、dp数组

• dp数组大小其实是根据自己的base case定义，设置出来的；
• dp数组的遍历方向是自己根据状态转移过程设计的，可以正向遍历，也可以反向遍历；
  • 只需要保证遍历之前，最优子结构的答案已经解出；
  • 遍历之后，该位置的答案被解出；

四、BASE CASE 和备忘录的初始值怎么定？

基于labuladong的算法网站，BASE CASE 和备忘录的初始值怎么定？；

力扣第931题，下降路径最小和；

[931]下降路径最小和//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int minFallingPathSum(int[][] matrix) {int length = matrix.length;memo = new int[length][length];// memo 初始化for (int i = 0; i < length; i++) {Arrays.fill(memo[i], Integer.MAX_VALUE);}// 找到最小值int res = Integer.MAX_VALUE;for (int j = 0; j < length; j++) {res = Math.min(res, dp(matrix, length - 1, j));}return res;}// 定义一个备忘录int[][] memo;// memo[i][j] 代表从第一行中的任何元素开始，到达i,j位置的下降路径最小和/*** @param matrix:整数数组* @param i：第i行* @param j：第j列* @return 从整数数组中第一行的仍和元素开始，达到第i行第j列的元素的下降路径最小和*/int dp(int[][] matrix, int i, int j) {// 判断是否越界if (i < 0 || j < 0 || i >= matrix.length || j >= matrix.length) {return Integer.MAX_VALUE;}// base caseif (i == 0) {// 如果是第一行的元素，那么就等于其本身return matrix[0][j];}// 判断 memo 中是否已经算出该位置的结果if (memo[i][j] != Integer.MAX_VALUE) {return memo[i][j];}// 否则开始算，进行状态转移memo[i][j] = matrix[i][j] + min(dp(matrix, i - 1, j), dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j + 1));return memo[i][j];}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));}
}
//leetcode submit region end(Prohibit modification and deletion)