概述：

? 算法的重要性是不言而喻的。

? 可能是你會不屑于聽這樣的話，是因為在我們的實際開發(fā)中，用到算法的地方真是太少了。對于這一點我并不否認，因為對于一個初級的開發(fā)者而言，算法顯得太過高深了。如果我們想去實現一個功能，通常的做法就是百度或是Google。這就是為什么會有那么一句調侃之辭：我們不生產代碼，我們只是代碼的搬運工。

? 當我們已經完成了初級開發(fā)者的這一過程時，我們應該想著怎么去優(yōu)化自己的代碼，從而讓自己的代碼更加優(yōu)美，也更顯B格。

動規(guī)的使用場景：

? 動態(tài)規(guī)劃是對回溯算法的一種改進。

? 我們知道回溯的一個致命缺點是它的重復計算，在后面的例子中我也會通過實例來說明這一點，而動規(guī)則規(guī)避了這個問題。動規(guī)的核心是狀態(tài)和狀態(tài)轉移方程。

示例例舉及過程說明：

? 1.數字三角形

??? 問題描述：

????? 有一個由非負整數組成的三角形，第一行只有一個數，除了最后一行之外每個數的左下方和右下方各有一個數。

????? 從第一行的數開始，每次可以往下或右下走一格，直到走到最后一行，把沿涂經過的數全部加起來。如何走才能使得這個數盡可能的大？

??? 思路梳理：

????? 對于這樣一個問題，可能大家想到的第一個解法就是遞歸。對于遞歸，我們不用想太多。因為當我們想要知道第(i, j)處的最大值時，是要依賴第(i +　1， j)和第(i + 1, j + 1)個節(jié)點的最大值。以此類推，如是我們就可以使用遞歸和遞推來實現。

??? 遞歸求解（關鍵代碼）

/*** 通過回溯法獲得第(i, j)處的最大值* @author Aaron* 2015年8月2日*/private static int getNodeMaxByRecall(int[][] m, int i, int j) {int max = Integer.MIN_VALUE;System.out.println("m[" + i + "][" + j + "]");max = m[i][j] + (i == m.length - 1 ? 0 : Math.max(getNodeMaxByRecall(m, i + 1, j), getNodeMaxByRecall(m, i + 1, j + 1)));return max;}/*** 回溯法求解* @author Aaron* 2015年8月1日*/public static void calculateByRecall(int[] a) {int[][] m = getMatrix(a);int max = getNodeMaxByRecall(m, 0, 0);System.out.println("max[0][0] = " + max);}
??? 可以看到，遞歸求解時是一種自頂向下的求解方式。它是在按需去計算。

??? 在遞歸中，比如說我們的意圖是去求解max(i, j)，當我們知道需要求解max(i, j)，就必須知道m(xù)ax(i + 1, j)和max(i + 1, j + 1)時，我們才去求解max(i + 1, j)和max(i + 1, j + 1).

???可是，這種按需求解的過程，無法讓我們知道，再要計算的點是否已經計算過了。下面是這個程序在遞歸的過程中計算過的節(jié)點過程：

???

???可以看到，這里有一些節(jié)點是被重復計算的。

??? 遞推法求解（關鍵代碼）：

/*** 通過遞推法獲得第(i, j)處的最大值* @author Aaron* 2015年8月2日*/private static int getNodeMaxByRecursion(int[][] m, int i, int j) {int max = Integer.MIN_VALUE;System.out.println("m[" + i + "][" + j + "]");max = m[i][j] + (i == m.length - 1 ? 0 : Math.max(m[i + 1][j], m[i + 1][j + 1]));return max;}/*** 遞推法求解* @author Aaron* 2015年8月2日*/private static void calculateByRecursion(int[] a) {int[][] m = getMatrix(a);for (int i = m.length - 1; i >= 0; i--) {for (int j = 0; j <= i; j++) {m[i][j] = getNodeMaxByRecursion(m, i, j);}}int max = m[0][0];System.out.println("max[0][0] = " + max);}
??? 可以看到，遞推求解時是一種自底向上的求解方式。它是在預先計算。

??? 在遞推中，比如說我們的意圖是去求解max(i, j)，當我們知道需要求解max(i, j)，就必須知道m(xù)ax(i + 1, j)和max(i + 1, j + 1)時，不過這個時候，我們的max(i + 1, j)和max(i + 1, j + 1)已經計算出來了，這個時候我們就不用再去計算了.

???在遞推的計算過程中，因為我們是自底向上的求解，所以我們并不知道這個節(jié)點是否會被使用到，而如果這個節(jié)點需要被使用，我們也不會重復計算這個值，因為已經計算過，并已經保存下來了。不過，這個過程中，每個節(jié)點都會被計算一次，不管會不會被使用（雖然這個程序中是都被使用了）。

???

??可以看到，這里每個節(jié)點有且僅有一次被調用了。時間復雜度上就有了一些優(yōu)勢。

??? 記憶化求解（關鍵代碼）：

/*** 通過記憶化搜索獲得第(i, j)處的最大值* @author Aaron* 2015年8月2日*/private static int getNodeMaxByMemory(int[][] m, int[][] d, int i, int j) {if (d[i][j] >= 0) {return d[i][j];}System.out.println("m[" + i + "][" + j + "]");d[i][j] = m[i][j] + (i == m.length - 1 ? 0 : Math.max(getNodeMaxByMemory(m, d, i + 1, j), getNodeMaxByMemory(m, d, i + 1, j + 1)));return d[i][j];}/*** 記憶化搜索* @author Aaron* 2015年8月2日*/private static void calculateByMemory(int[] a) {int[][] m = getMatrix2(a);int[][] d = initMatrix(m.length);int max = getNodeMaxByMemory(m, d, 0, 0);System.out.println("max[0][0] = " + max);}
??? 記憶化搜索是基于遞歸來進行的。因為我們想做一件事，來避免之前在遞歸中的重復計算。在學習算法的復雜度的時候，我們知道復雜度分為兩種，一種是時間復雜度，一種是空間復雜度。這兩種復雜度是有一個平衡的。也就是說我們想要在時間上優(yōu)化，那么空間上就得做出犧牲。這里也正是使用了犧牲空間來換取時間的優(yōu)先。

??? 下面是各個節(jié)點被計算的過程：

???

??? 這里可以看到，我們的每個節(jié)點也是只被計算了一次。節(jié)省了時間。

? 2.鋼條切割

? 問題描述：

? 給定一段長度為n英寸的鋼條和一個價格表p(i)，求切割鋼條的方案，使得銷售收益r(n)最大。注意，如果長度為n英寸的鋼條的價格為p(n)足夠大，最優(yōu)解可能不是完全不需要切割。

? 價格表：

?

? 看到這一個問題，不知道大家是不是也跟我一樣，第一感覺是可以使用貪心試一下?？墒羌毾胫笥职l(fā)現行不通，因為這里面如果按不同的方式切割鋼條，那么切割成的兩份都是可變的量，不好控制。

? 按照上面的思路，我們可以使用兩種方法來試著解決這一問題：

? 遞歸（關鍵代碼）：

/*** 計算長度為n的鋼條的最佳切割方案(遞歸)* @author Aaron* 2015年8月3日*/private static int getMax(int[] p, int n) {System.out.println(n);if (n <= 0) {return 0;}int max = Integer.MIN_VALUE;for (int i = 1; i <= n; i++) {max = Math.max(max, p[i - 1] + getMax(p, n - i));}return max;}/*** 通過遞歸計算鋼條的切割算法* @author Aaron* 2015年8月3日*/private static void calculateMaxByRecursive(int n) {initPriceList();int[] p = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};int max = getMax(p, n);System.out.println("max = " + max);}

? 記憶化搜索（關鍵代碼）：

private static int[] getRecordArray(int n) {if (n <= 0) {return null;}int[] r = new int[n];for (int i = 0; i < n; i++) {r[i] = Integer.MIN_VALUE;}return r;}/*** 計算長度為n的鋼條的最佳切割方案(記憶化搜索)* @author Aaron* 2015年8月3日*/private static int getMaxByMemory(int[] p, int n, int[] r) {if (n <= 0) {return 0;}if (r[n] >= 0) {return r[n];}System.out.println(n);int max = Integer.MIN_VALUE;for (int i = 1; i <= n; i++) {max = Math.max(max, p[i - 1] + getMaxByMemory(p, n - i, r));}r[n] = max;return max;}/*** 通過記憶化搜索計算鋼條的切割算法* @author Aaron* 2015年8月3日*/private static void calculateMaxByMemory(int n) {initPriceList();int[] p = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};int[] r = getRecordArray(n + 1);int max = getMaxByMemory(p, n, r);System.out.println("max = " + max);}

完整源代碼下載：

http://download.csdn.net/detail/u013761665/8957807

總結

以上是生活随笔為你收集整理的算法之动态规划初步（Java版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。