背景
遞歸實現是出了名的消耗內存以及時間復雜度大秆吵，尤其是在有很多子問題重復計算的情況下淮椰。這個時候我們一般通過動態(tài)規(guī)劃的手段，去做記憶性搜索纳寂，那么如何將遞歸轉化成動態(tài)規(guī)劃呢主穗。我們來通過斐波那契數列這個例子來展開：
例子
斐波那契的遞歸實現：
private static long func(int n) {
if (n == 0 || n == 1){
return 1;
} else {
return func(n - 1) + func(n - 2);
}
}
斐波那契的DP實現：
private static long dpFunc(int n) {
//構建狀態(tài)轉移矩陣
long state[] = new long[n+1];
//初始化狀態(tài)轉移矩陣
state[0] = 1;
state[1] = 1;
//狀態(tài)轉移方程
for (int i=2;i<=n;i++) {
state[i] = state[i - 1] + state[i - 2];
}
return state[n];
}
步驟
遞歸到動規(guī)的一般轉化方法：
1.創(chuàng)建狀態(tài)轉移矩陣
遞歸函數有n個參數，就定義一個n維的數組烈疚，數組的下標是遞歸函數參數的取值范圍黔牵，數組元素的值是遞歸函數的返回值
2.初始化狀態(tài)轉移矩陣
這樣就可以從邊界值開始， 逐步填充數組爷肝，相當于計算遞歸函數值的逆過程猾浦。
3.狀態(tài)轉移方程
構建矩陣元素的新循環(huán)；
遞歸的方法名替換為矩陣名灯抛；遞歸的方法入參替換為矩陣元素金赦；遞歸的方法返回參數替換為矩陣元素；
返回結果替換為矩陣中的末位元素对嚼。
