[[399414]]

本文轉(zhuǎn)載自微信公眾號「Java極客技術(shù)」，作者鴨血粉絲 。轉(zhuǎn)載本文請聯(lián)系Java極客技術(shù)公眾號。

Hello 大家好，我是阿粉，前面有篇文章給大家介紹了動態(tài)規(guī)劃，并通過兩個案例給大家演示，后臺很多小伙伴也提供了很多建議，沒看過的小伙伴可以去看下什么是動態(tài)規(guī)劃——從青蛙跳臺階開始了解。今天再給大家介紹兩個案例，幫助大家更好的掌握也順便回顧一下。

案例 1

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

思考

根據(jù)上篇文章提供的思路，我們依次進行相關(guān)的步驟：

1. 定義變量：我們定義從左上角走到(i, j) 這個位置時，最小的路徑和是 dp[i - ][j - 1]。那么，dp[m-1] [n-1] 就是我們要的答案;
2. 尋找關(guān)系：dp[i][j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]; arr[i][j] 表示網(wǎng)格中的數(shù)值，到達當前格子的最小路徑等于左邊或者上邊中較小的路徑加上格子本身的數(shù)值;
3. 定義初始值：dp[i][0] = dp[i-1][0] + arr[i][0];，dp[0][i] = dp[0][i-1] + arr[0][i];;第一行或者第一列的時候就是整行和整列的數(shù)值累加。

編碼

上面的分析可以想到，那么接下來我們就需要用代碼來實現(xiàn)了，對于需要使用到之前的記錄，我們可以考慮用二維數(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)建了一個二維數(shù)組 dp[m][n]，用于記錄到達位置的最短路徑，由于當前的路徑是由左邊或者上邊的最小路徑加上當前格子的數(shù)值得到。這里我們需要找到對應(yīng)關(guān)系，也就是dp[i][j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]，這里我們需要取相鄰的最小值再加上當前格子的數(shù)值。

案例 2

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

思考

1. 定義變量：定義 dp[i] 表示湊成金額i，所需要的最少硬幣個數(shù)，即 dp[amount] 則是我們需要求解的;
2. 尋找關(guān)系：假設(shè)我們有三種硬幣a，b，c，兌換的金幣數(shù)為 m，我們可以推出 dp[m] = min(dp[m - a], dp[m - b], dp[m - c]) + 1，因為如果我們是需要求 m 金額的最少硬幣個數(shù)，如果我們求出了 m - a 金額需要的硬幣個數(shù)，在加上一個 a 就可以得到 m，硬幣個數(shù)只要加 1。其實b，c 同理。并且我們需要取所有硬幣種類的最小數(shù)。
3. 定義初始值：dp[0] = 0，沒有金額當時也不需要硬幣個數(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++) { 
            #賦值，當不能組合和輸出 -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]; 
    } 

總結(jié)

動規(guī)劃的題目在 LeetCode 上面有很多，大家可以根據(jù)上面提供的思路去多刷幾道題，慢慢就會有感覺了，刷完動態(tài)規(guī)劃的題目，相信對大家工作或者找工作肯定有很大的幫助。https://leetcode-cn.com/problemset/all/?topicSlugs=dynamic-programming