动态规划——入门（1）
被動態算法折磨的我看到了大神的這篇文章，覺得明白了許多，轉載過來，以便回顧。然沒詢問大神意見，望諒解
大神使用C++寫的，我這代碼是java
原文地址為：https://blog.csdn.net/baidu_28312631/article/details/47418773
動態規劃相信大家都知道，動態規劃算法也是新手在剛接觸算法設計時很苦惱的問題，有時候覺得難以理解，但是真正理解之后，就會覺得動態規劃其實并沒有想象中那么難。網上也有很多關于講解動態規劃的文章，大多都是敘述概念，講解原理，讓人覺得晦澀難懂，即使一時間看懂了，發現當自己做題的時候又會覺得無所適從。我覺得，理解算法最重要的還是在于練習，只有通過自己練習，才可以更快地提升。話不多說，接下來，下面我就通過一個例子來一步一步講解動態規劃是怎樣使用的，只有知道怎樣使用，才能更好地理解，而不是一味地對概念和原理進行反復琢磨。
首先，我們看一下這道題（此題目來源于北大POJ）：
數字三角形(POJ1163)
在上面的數字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經過的數字之和最大。路徑上的每一步都只能往左下或 右下走。只需要求出這個最大和即可，不必給出具體路徑。 三角形的行數大于1小于等于100，數字為 0 - 99
輸入格式：
5 //表示三角形的行數 接下來輸入三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
要求輸出最大和
接下來，我們來分析一下解題思路：
首先，肯定得用二維數組來存放數字三角形
然后我們用D( r, j) 來表示第r行第 j 個數字(r,j從1開始算)
我們用MaxSum(r, j)表示從D(r,j)到底邊的各條路徑中，最佳路徑的數字之和。
因此，此題的最終問題就變成了求 MaxSum(1,1)
當我們看到這個題目的時候，首先想到的就是可以用簡單的遞歸來解題：
D(r, j)出發，下一步只能走D(r+1,j)或者D(r+1, j+1)。故對于N行的三角形，我們可以寫出如下的遞歸式
根據上面這個簡單的遞歸式，我們就可以很輕松地寫出完整的遞歸代碼:
package other_demo;import java.util.Scanner;public class dp {static int n;public static int MaxSum(int i,int j,int[][] num) {if(i==n-1) {return num[i][j];}return Math.max(MaxSum(i+1, j, num),MaxSum(i+1, j+1, num))+num[i][j];}public static void main(String[] args) {Scanner sc=new Scanner(System.in);n=sc.nextInt();int[][] num=new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {num[i][j]=sc.nextInt();}}System.out.println("最大路徑為："+MaxSum(0, 0,num));} }但是上面這個代碼的運行時間會很長，因為我們重復計算了，當我們在進行遞歸時，計算機幫我們計算的過程如下圖：
就拿第三行數字1來說，當我們計算從第2行的數字3開始的MaxSum時會計算出從1開始的MaxSum，當我們計算從第二行的數字8開始的MaxSum的時候又會計算一次從1開始的MaxSum，也就是說有重復計算。這樣就浪費了大量的時間。也就是說如果采用遞規的方法，深度遍歷每條路徑，存在大量重復計算。則時間復雜度為 2的n次方,對于 n = 100 行，肯定超時。
接下來，我們就要考慮如何進行改進，我們自然而然就可以想到如果每算出一個MaxSum(r,j)就保存起來，下次用到其值的時候直接取用，則可免去重復計算。那么可以用n方的時間復雜度完成計算。因為三角形的數字總數是 n(n+1)/2。
根據這個思路，我們就可以將上面的代碼進行改進，使之成為記憶遞歸型的動態規劃程序：
雖然在短時間內就AC了。但是，我們并不能滿足于這樣的代碼，因為遞歸總是需要使用大量堆棧上的空間，很容易造成棧溢出，我們現在就要考慮如何把遞歸轉換為遞推，讓我們一步一步來完成這個過程。
我們首先需要計算的是最后一行，因此可以把最后一行直接寫出，如下圖：
現在開始分析倒數第二行的每一個數，現分析數字2，2可以和最后一行4相加，也可以和最后一行的5相加，但是很顯然和5相加要更大一點，結果為7，我們此時就可以將7保存起來，然后分析數字7，7可以和最后一行的5相加，也可以和最后一行的2相加，很顯然和5相加更大，結果為12，因此我們將12保存起來。以此類推。。我們可以得到下面這張圖：
然后按同樣的道理分析倒數第三行和倒數第四行，最后分析第一行，我們可以依次得到如下結果：
上面的推導過程相信大家不難理解，理解之后我們就可以寫出如下的遞推型動態規劃程序：
我們的代碼僅僅是這樣就夠了嗎？當然不是，我們仍然可以繼續優化，而這個優化當然是對于空間進行優化，其實完全沒必要用二維maxSum數組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。
對于空間優化后的具體遞推過程如下:
接下里的步驟就按上圖的過程一步一步推導就可以了。進一步考慮，我們甚至可以連maxSum數組都可以不要，直接用D的第n行直接替代maxSum即可。但是這里需要強調的是：雖然節省空間，但是時間復雜度還是不變的。
依照上面的方式，我們可以寫出如下代碼:
作者：ChrisYoung1314
來源：CSDN
原文：https://blog.csdn.net/baidu_28312631/article/details/47418773
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！
總結
以上是生活随笔為你收集整理的动态规划——入门（1）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 杂记（1）java读取char类型2.
- 下一篇： 树，森林与二叉树之间的转换