如何实现动态规划进阶

本篇内容介绍了“如何实现动态规划进阶”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

案例 1

问：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小，其中 arr[m][n]  表示具体的值。每次只能向下或者向右移动一步。

思考

我们依次进行相关的步骤：

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 定义变量：我们定义从左上角走到(i, j) 这个位置时，最小的路径和是 dp[i - ][j - 1]。那么，dp[m-1] [n-1]  就是我们要的答案;

3. 寻找关系：dp[i][j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]; arr[i][j]  表示网格中的数值，到达当前格子的最小路径等于左边或者上边中较小的路径加上格子本身的数值;

4. 定义初始值：dp[i][0] = dp[i-1][0] + arr[i][0];，dp[0][i] = dp[0][i-1] +  arr[0][i];;第一行或者第一列的时候就是整行和整列的数值累加。

编码

上面的分析可以想到，那么接下来我们就需要用代码来实现了，对于需要使用到之前的记录，我们可以考虑用二维数组来记录，所以就有了下面的这段代码。

public int dp(int[][] arr) {     int m = arr.length;    int n = arr[0].length;     if (m <=0 || n <= 0) {         return 0;     }     int[][] dp = new int[m][n];     // 初始化    dp[0][0] = arr[0][0];    // 初始化最左边的列    for(int i = 1; i < m; i++){       dp[i][0] = dp[i-1][0] + arr[i][0];     }    // 初始化最上边的行    for(int i = 1; i < n; i++){       dp[0][i] = dp[0][i-1] + arr[0][i];     }          for (int i = 1; i < m; i++) {         for (int j = 1; j < n; j++) {             dp[i][j] = Math.min(dp[i-1][j]，dp[i][j-1]) + arr[i][j];         }     }     return dp[m - 1][n - 1]; }

解释下上面的代码，首先我们创建了一个二维数组  dp[m][n]，用于记录到达位置的最短路径，由于当前的路径是由左边或者上边的最小路径加上当前格子的数值得到。这里我们需要找到对应关系，也就是dp[i][j]  = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]，这里我们需要取相邻的最小值再加上当前格子的数值。

案例 2

问：给定不同面额的硬币 coins 和一个总金额  amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回  -1。你可以认为每种硬币的数量是无限的。Leetcode 322. 零钱兑换。

思考

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 定义变量：定义 dp[i] 表示凑成金额i，所需要的最少硬币个数，即 dp[amount] 则是我们需要求解的;

3. 寻找关系：假设我们有三种硬币a，b，c，兑换的金币数为 m，我们可以推出 dp[m] = min(dp[m - a], dp[m - b], dp[m -  c]) + 1，因为如果我们是需要求 m 金额的最少硬币个数，如果我们求出了 m - a 金额需要的硬币个数，在加上一个 a 就可以得到 m，硬币个数只要加  1。其实b，c 同理。并且我们需要取所有硬币种类的最小数。

4. 定义初始值：dp[0] = 0，没有金额当时也不需要硬币个数，dp[i - coins[j] 需要有解;

编码

public int dp(int[] coins, int amount) {          int[] dp = new int[amount + 1];         int size = coins.length;         int i = 0;         int j = 0;      # 定义初始值         dp[0] = 0;         for (i = 1; i <= amount; i++) {             #赋值，当不能组合和输出 -1 判断使用             dp[i] = Integer.MAX_VALUE;            # 遍历 coins 中的硬币种类             for (j = 0; j < size; j++) {                 if (i >= coins[j] && (dp[i - coins[j]]) != Integer.MAX_VALUE) {                     dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);                 }             }         }         if (dp[amount] == Integer.MAX_VALUE) {             dp[amount] = -1 ;         }         return dp[amount];     }

“如何实现动态规划进阶”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！