如何實現動態規劃進階

本篇內容介紹了“如何實現動態規劃進階”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

案例 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];     }

“如何實現動態規劃進階”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！