前言：最近做各大廠的筆試題，發現動态規劃和排列組合的題挺多的，于是認真研究了一下，寫在這裡備忘。
1.先抛出數學上的公式
當a=b=1的時候，該二項式變成了
，這就是二進制下的遞推關系了。
雖然二項式有很多特性，但是在計算機中我們隻關注兩個特征：即遞推關系和邊界條件，對應着兩個公式：
也就是動态規劃的狀态方程和初始狀态，如上圖所示的兩個關系，這樣看着很抽象，那麼先看如下圖的推導：
通過二項式與楊輝三角型的對比可以出它們是一一對應的，由此也就得出了這個重要的遞推關系：
它表示任意時刻 ( 第k個時刻，k是介于[0-n]之間任意的值) 的中間狀态，都是可以由上以時刻的值遞推出來的，這是二項式與楊輝三角型直覺對應得出的公式，當然也可以通過數學證明(太麻煩省略)。
因為計算機的變量在某一個時刻隻能存一個值，這個值可以由之前的變量推出來，是以建立了依賴關系，用遞推關系來求解問題就可以保證在多項式時間複雜度内完成，比暴力搜尋要快。同時為了避免重複計算先前的結果，是以使用一個二維表(矩陣)來緩存結果。那麼按照楊輝三角型的特點，相鄰兩個子結果，也就是矩陣的元素(表示子結果的狀态)，是按照上述關系依賴的。
動态規劃中通常是從結果向開始逆向遞推，結束條件就是另外一個公式：
。
是以排列組合公式：
就可以用動态規劃的方式推出來。
是以動态規劃三個主要步驟：1.抽象出目前的狀态；2.确定遞推關系(也就是狀态方程)；3.确定初始條件(邊界)。
1.目前狀态即：i表示什麼，j表示什麼，dp[i][j]表示什麼
2.遞推關系即：
，這是一個模版公式，對于不同的題目/場景會不同，核心思想是找到如果有上一個結果推出目前的結果，以楊輝三角形為例，目前值應該其上一行的目前列k 和目前列的左邊一列k-1之和。對于01背包問題，目前物品為i，如果不選它，則是m[i-1][j]，如果選了它則是m[i-1][j-w[i]]+vi，選和不選的兩個值則是有上一個狀态的兩個相鄰結果推出來的。01背包問題見下圖。
3.初始條件即：
，初始時的狀态，通常要手動指派，也就是矩陣dp[n+1][m+1]的第一行和第一列。
代碼：
同樣地，對于某筆試題： 小Q歌單、合唱團(自行百度題目)， 都可以按照
的思想快速确立狀态方程。
小Q歌單：就是以楊輝三角形來存所有的組合項：
合唱團：從n個元素中選擇k個，使這k個元素的乘積最大
有 n 個學生站成一排，每個學生有一個能力值，牛牛想從這 n 個學生中按照順序選取 k 名學生，
要求相鄰兩個學生的位置編号的差不超過 d，使得這 k 個學生的能力值的乘積最大，求最大的乘積？
先這樣把，後面再整理。
突然覺得數學和計算機息息相關啊，後悔當初數學沒學好。