在刷劍指offer和LeetCode中發現，動態規劃是經常出現的一類題目，那么接下來我們就來仔細分析和總結下其中的套路，
介紹
動態規劃（DP）說白了其實就是一種求解最優解的方法，是一種比較特殊的分治思想，利用它可以對時間復雜度進行優化，其主要是根據狀態轉移方程來進行求解，
其內部包含了主要的兩種思想就是分治和貪心，
解題思路
總體來說動態規劃題目的解題思路就四步：
- 狀態表示
- 轉移方程
- 初始狀態
- 最終狀態
下面我們詳細的說明一下這四步，在剛開始的時候我們需要構建一個存盤資料的表格，一般使用陣列居多，然后通過分析題目找出存在的狀態轉移方程，即從上一個狀態到下一個狀態是如何變化的，然后根據題目設定我們的初始值，然后根據狀態轉移方程重復計算，在此程序中利用到了前面積累下來的記錄，所以能夠加快速度，最后一直倒找最終我們所需要的狀態，
真題演練
我們這邊拿劍指offer中的第47題禮物的最大價值這個典型的題目來舉例讓大家明白這個演算法的思路
連續子陣列的最大和
題目：
在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0），你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角，給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？
解法
本文說了是講解動態規劃的肯定是要用動態規劃來解決這個問題，那我們就按照我們的步驟來進行
- 狀態表示
設動態規劃矩陣dp[][]，其中dp[i][j]表示從棋盤的左上角開始到達單元格(i,j)時能拿到禮物的最大累計價值
- 轉移方程
由于只能向右或者向下移動，所以：
-
- 當i=0且j=0，為起始元素
- 當i=0且j≠0，為第一行元素，只能左邊到達
- 當i≠0且j=0，為第一列元素，只能上邊達到
- 當i≠0且j不等于0，可從上邊或者左邊到達
所以，狀態轉移方程如下所示：
- 初始狀態
從上面分析我們可以知道dp[0][0]=grid[0][0]
- 最終狀態
最終狀態就是我們遍歷完即dp[m-1][n-1]，回傳dp陣列中右下角的元素
java實作
有了思路后面就是java的實作，如下所示：
class Solution {
public int maxValue(int[][] grid) {
int row = grid.length;
int column = grid[0].length;
//dp[i][j]表示從grid[0][0]到grid[i - 1][j - 1]時的最大價值
int[][] dp = new int[row + 1][column + 1];
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= column; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
}
}
return dp[row][column];
}
}
總結
這些就是動態規劃的所有內容了，作為一個在LeetCode中和面試中都經常出現的題目，可以說是必須要掌握起來了，總之就是關注四件事情：
- 狀態表示
- 轉移方程
- 初始狀態
- 最終狀態
其中最難的就是轉移方程，這個要根據各個題目靈活處理，或者多做一些題目總結也可以獲得不錯的識訓和進步，只要有了狀態轉移方程，后面的初始狀態和邊界值再多加注意就沒有什么大問題了，
最后
- 如果覺得看完有識訓，希望能關注一下，順便給我點個贊，這將會是我更新的最大動力，感謝各位的支持
- 歡迎各位關注我的公眾號【java冢狐】，專注于java和計算機基礎知識，保證讓你看完有所識訓，不信你打我
- 求一鍵三連：點贊、轉發、在看，
- 如果看完有不同的意見或者建議，歡迎多多評論一起交流，感謝各位的支持以及厚愛，
——我是冢狐，和你一樣熱愛編程，
歡迎關注公眾號“Java冢狐”獲取最新訊息
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255060.html
標籤：Java
上一篇：Nginx快速入門