如何實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃進(jìn)階

本篇內(nèi)容介紹了“如何實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃進(jìn)階”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

案例 1

問：給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小，其中 arr[m][n]  表示具體的值。每次只能向下或者向右移動(dòng)一步。

思考

我們依次進(jìn)行相關(guān)的步驟：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 定義變量：我們定義從左上角走到(i, j) 這個(gè)位置時(shí)，最小的路徑和是 dp[i - ][j - 1]。那么，dp[m-1] [n-1]  就是我們要的答案;

3. 尋找關(guān)系：dp[i][j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]; arr[i][j]  表示網(wǎng)格中的數(shù)值，到達(dá)當(dāng)前格子的最小路徑等于左邊或者上邊中較小的路徑加上格子本身的數(shù)值;

4. 定義初始值：dp[i][0] = dp[i-1][0] + arr[i][0];，dp[0][i] = dp[0][i-1] +  arr[0][i];;第一行或者第一列的時(shí)候就是整行和整列的數(shù)值累加。

編碼

上面的分析可以想到，那么接下來我們就需要用代碼來實(shí)現(xiàn)了，對(duì)于需要使用到之前的記錄，我們可以考慮用二維數(shù)組來記錄，所以就有了下面的這段代碼。

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

解釋下上面的代碼，首先我們創(chuàng)建了一個(gè)二維數(shù)組  dp[m][n]，用于記錄到達(dá)位置的最短路徑，由于當(dāng)前的路徑是由左邊或者上邊的最小路徑加上當(dāng)前格子的數(shù)值得到。這里我們需要找到對(duì)應(yīng)關(guān)系，也就是dp[i][j]  = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]，這里我們需要取相鄰的最小值再加上當(dāng)前格子的數(shù)值。

案例 2

問：給定不同面額的硬幣 coins 和一個(gè)總金額  amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回  -1。你可以認(rèn)為每種硬幣的數(shù)量是無限的。Leetcode 322. 零錢兌換。

思考

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 定義變量：定義 dp[i] 表示湊成金額i，所需要的最少硬幣個(gè)數(shù)，即 dp[amount] 則是我們需要求解的;

3. 尋找關(guān)系：假設(shè)我們有三種硬幣a，b，c，兌換的金幣數(shù)為 m，我們可以推出 dp[m] = min(dp[m - a], dp[m - b], dp[m -  c]) + 1，因?yàn)槿绻覀兪切枰?m 金額的最少硬幣個(gè)數(shù)，如果我們求出了 m - a 金額需要的硬幣個(gè)數(shù)，在加上一個(gè) a 就可以得到 m，硬幣個(gè)數(shù)只要加  1。其實(shí)b，c 同理。并且我們需要取所有硬幣種類的最小數(shù)。

4. 定義初始值：dp[0] = 0，沒有金額當(dāng)時(shí)也不需要硬幣個(gè)數(shù)，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++) {             #賦值，當(dāng)不能組合和輸出 -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];     }

“如何實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃進(jìn)階”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！