有些暴力遞歸不能被改成動態(tài)規(guī)劃，因為他本身要求的解空間無法被壓縮了。

eg：漢諾塔問題，我們必須打印那些步驟。

如果要寫一個動態(tài)規(guī)劃，先寫成暴力遞歸的版本，然后模板化修改。

先寫遞歸版本：

不妨記遞歸函數(shù)是f（）

1.base case 是啥？

如果這個點在右下角，直接返回這個點的數(shù)值就可以了。 a[i][j]

如果這個點在最后一行。 返回當(dāng)前位置的數(shù)字+下一步需要的

即： a[i][j] + f[i][j+1]

如果在最后一列

同理 a[i][j] +f[i+1][j]

一般情況：就當(dāng)前加 右或下的最小值。

#include <iostream> #include <algorithm> using namespace std; const int N=10010;int walk(int a[N][N],int rows,int columns,int i,int j){if(i==rows-1 && j==columns-1){return a[i][j];}if(i==rows-1) return a[i][j]+walk(a,rows,columns,i,j+1);if(i==columns-1) return a[i][j]+walk(a,rows,columns,i+1,j);return a[i][j]+min(walk(a,rows,columns,i,j+1),walk(a,rows,columns,i+1,j)); }

如果改成非遞歸的動態(tài)規(guī)劃呢？

首先要思考，什么樣的遞歸可以被改成動態(tài)規(guī)劃？

設(shè)這個遞歸函數(shù)是f（0,0） 表示從0 0 位置走到右下角

f(0,0) 會調(diào)用 f(0 1) and f(1 0)

f(0 1) 會調(diào)用 f(1 1) and f(0 2)

f(1 0) 會調(diào)用 f(1 1) and f(2 0)

f（1 1）算過兩次，我們可以省去這個步驟

記錄f 1 1 狀態(tài)，下次用上直接拿出來用，就可以節(jié)省時間了。

to sum up，當(dāng)一個遞歸有重復(fù)狀態(tài)。 并且這個狀態(tài)與到達(dá)他的路徑無關(guān)。

不管怎么走到達(dá)這個位置，對應(yīng)的狀態(tài)函數(shù)返回值都是一樣的，就可以被記錄下來，下次再用。

這樣的過程，我們稱作：

無后效性問題。

狀態(tài)的參數(shù)定了，返回值就定了。

之前的選擇無法影響當(dāng)前的狀態(tài)。

那么參數(shù)的不同就可以 確定不同的返回值。

對應(yīng)這個問題，參數(shù)是 i j 返回值根據(jù)i j的不同，值也不同。

f函數(shù)也是一張二維矩陣。

我們需要的就是f 0 0 位置的返回值。

回到遞歸函數(shù)中，找到對應(yīng)的base case 然后填在新的表里。

可以發(fā)現(xiàn)： 遞歸是順著來，動態(tài)規(guī)劃是反著回去的。

總結(jié)

以上是生活随笔為你收集整理的汉诺塔递归的空间复杂度_暴力递归与动态规划 1.0的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。