個人業余愛好：以后會堅持每天至少一篇新隨筆，希望大家多多監督、支持和交流～
摘要：這是博主第一篇追隨演算法學習的心得體會，關于一道簡單的動態規劃題目，力求簡明扼要，聚焦交流學習～
正題：
1.拋出題目（對問題的初步理解）：
* 眾所周知，牛妹有很多很多粉絲，粉絲送了很多很多禮物給牛妹，牛妹的禮物擺滿了地板，
* 地板是
* N×M的格子，每個格子有且只有一個禮物，牛妹已知每個禮物的體積，
* 地板的坐標是左上角(1,1) 右下角（N, M），
* 牛妹只想要從屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步
* 每次走過一個格子，拿起（并且必須拿上）這個格子上的禮物，
* 牛妹想知道，她能走到最后拿起的所有禮物體積最小和是多少?
題目出處：https://www.nowcoder.com/practice/c4f777778e3040358e1e708750bb7fb9?tpId=110&tqId=33431&tPage=1&rp=1&ru=%2Fta%2Fjob-code&qru=%2Fta%2Fjob-code%2Fquestion-ranking
2.輸入輸出示例（舉一反三的理解題意，明確題目要實作的演算法初始引數和最侄訓傳）：
輸入：[[1,2,3],[2,3,4]]
輸出：7
說明：按路徑：（1,1）-> (1,2) -> (2,3) 走得到最小值，
3.分析：
一言可以概之，滿足最優化問題最關鍵的兩大必要條件：無后效性（未來決策與過去決策無關）和最優子策略（子問題可用同理的決策方法解決），是一道典型的動態規劃問題，而且是動規中最簡單的線性動規（通過線性結構解決足矣），
4.例程：
/**
* 眾所周知，牛妹有很多很多粉絲，粉絲送了很多很多禮物給牛妹，牛妹的禮物擺滿了地板，
* 地板是
* N×M的格子，每個格子有且只有一個禮物，牛妹已知每個禮物的體積，
* 地板的坐標是左上角(1,1) 右下角（N, M），
* 牛妹只想要從屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步
* 每次走過一個格子，拿起（并且必須拿上）這個格子上的禮物，
* 牛妹想知道，她能走到最后拿起的所有禮物體積最小和是多少?
* 問題判型：最優化問題
* 解決方案：動態規劃
* 逆向狀態轉換：如何走到右下方，首先前一步須要在右下方的周圍，推出走到格子（n,m）的禮物體積最小和的狀態轉移方程：
* min[n][m] = min{min[n - 1][m], min[n - 1][m - 1], min[n][m - 1]} + a[n][m]
* 同時要檢查計算出來的方程是否有解，須要滿足的條件是：
* 1.有初始值（通常都可以顯然可見）
* 2.迭代收斂（確保有最侄訓傳）
* 3.存在使迭代子均有符合定義的值（迭代子是指min[n - 1][m],min[n - 1][m - 1], min[n][m - 1]這些迭代元素，其值均要符合題意定義）的迭代順序
*/
public class NowSisterGiftSolution {
public static int selectPresent (int[][] presentVolumn) {
// write code here
if (null == presentVolumn) {
return -1;
}
if (presentVolumn.length == 0) {
return 0;
}
int[][] min = new int[presentVolumn.length][presentVolumn[0].length];
for (int i = 0; i < presentVolumn.length; i++) {
for (int j = 0; j < presentVolumn[i].length; j++) {
int m = 0;
if (i > 0) {
m = Math.min(min[i - 1][j], j > 0 ? min[i - 1][j - 1] : Integer.MAX_VALUE);
}
if (j > 0) {
m = Math.min(min[i][j - 1], m > 0 ? m : Integer.MAX_VALUE);
}
min[i][j] = m + presentVolumn[i][j];
}
}
return min[presentVolumn.length - 1][presentVolumn[0].length - 1];
}
public static void main(String[] strings) {
int[][] a = {{1,2,3},{2,3,4}};
int s = selectPresent(a);
System.out.println(s);
}
}
5.總結：
無論解決什么問題，實作是術，思路才是道；整道題下來，我的術在于實作的示例程式，而關鍵點在于建立狀態轉移方程的思路，逆向推導，理清正確迭代的決策如何通過計算實作，這才是此道題的道，另外，顯然，遞回也是可行的實作，在此不再贅述，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47525.html
標籤：其他