DP算法（動态規劃算法）

前幾天做leetcode的算法題很多題都提到了動态規劃算法，那麼什麼是動态規劃算法，它是什麼樣的思想，适用于什麼場景，就是我們今天的主題。

首先我們提出所有與動态規劃有關的算法文章中都會提出的觀點：　将一個問題拆成幾個子問題，分别求解這些子問題，即可推斷出大問題的解。

什麼都不了解的話看到這句話是懵逼的，我們也先略過，等看完整篇文章再回過頭來看一看這個觀點。

下面正式開始。

首先我們來看這個譯名，動态規劃算法。這裡的動态指代的是遞推的思想，算法在實作的過程中是動态延伸的，而不是提前控制的。規劃指的是需要我們給出動态延伸的方法和方向。

這兩個就是算法的問題點。

我們來看看這其中規劃的展現部分，規劃展現在情況分類上，我們隻有三種錢币，是以會要求實作f[n]中的n要大于某一個規定值才是可取的，要10元時候我們不可以取出11元，是以在這部分要進行單獨判斷。

再說動态部分，顯然，f[4],f[10],f[14]是我們需要單獨去計算的，那麼如何計算呢，就需要他們動态的去遞推下一步如何計算。

來看看這個式子：f(n)=min{f(n-1),f(n-5),f(n-11)}+1

顯然f(n)直接由後三個值決定，我們隻要算出這三個值即可，而這三個值又由同樣式的更小值決定，隻要得出更小值，甚至最小值，我們就可以推導出f(n)。

實際上是一種備援資訊的反向篩查算法，是暴力枚舉的簡化。

來看看使用dp算法的要求。

這也同時揭示了我一開始寫的那句話，大問題由小問題累積而成，是必要的。

實際的例子我用前兩天的幾道動态規劃的算法題來舉例。

一道一道來：

1.delete operation for two strings

java：

這裡的特殊點在于需要每一步都比較，也就是[i-1][j]與[j][i-1]，而不是[i][j]；

5就不說了，是标準的最長公共子序列問題，上一道問題的縮減版，注意的是由于要求最長長度，是以用的是max。

6.​​regular expression matching​​

這道題考慮到一個問題點就是在特殊情況下的判斷問題，我們抛開matches函數再看這道題的話，流程是一樣的，建立，問題拆分，傳回。

一般難點在于問題拆分部分，想要節省空間可以從建立部分下手，部分情況下可以降低數組次元。

以上。

（其實比較難的題，我自己拆分問題很多情況下也拆不好hhhhh，看看題解吧。）