鏈接：
很特別的一個動態(tài)規(guī)劃入門教程
動態(tài)規(guī)劃與貪心算法的區(qū)別與聯(lián)系

那么遇到問題如何用動態(tài)規(guī)劃去解決呢？根據(jù)上面的分析我們可以按照下面的步驟去考慮：
1、構(gòu)造問題所對應的過程。
2、思考過程的最后一個步驟，看看有哪些選擇情況。
3、找到最后一步的子問題，確保符合“子問題重疊”，把子問題中不相同的地方設(shè)置為參數(shù)。
4、使得子問題符合“最優(yōu)子結(jié)構(gòu)”。
5、找到邊界，考慮邊界的各種處理方式。
6、確保滿足“子問題獨立”，一般而言，如果我們是在多個子問題中選擇一個作為實施方案，而不會同時實施多個方案，那么子問題就是獨立的。
7、考慮如何做備忘錄。
8、分析所需時間是否滿足要求。
9、寫出轉(zhuǎn)移方程式。

   有一書店引進了一套書，共有3卷，每卷書定價是60元，書店為了搞促銷，推出一個活動，活動如下：
  
   如果單獨購買其中一卷，那么可以打9.5折。
   如果同時購買兩卷不同的，那么可以打9折。
   如果同時購買三卷不同的，那么可以打8.5折。
  
   如果小明希望購買第1卷x本，第2卷y本，第3卷z本，那么至少需要多少錢呢？（x、y、z為三個已知整數(shù)）。

   當然，這道題完全可以不用動態(tài)規(guī)劃來解，但是現(xiàn)在我們是要學習動態(tài)規(guī)劃，因此請想想如何用動態(tài)規(guī)劃來做？

   答案：
   1、過程為一次一次的購買，每一次購買也許只買一本（這有三種方案），或者買兩本（這也有三種方案），或者三本一起買（這有一種方案），最后直到買完所有需要的書。
   2、最后一步我必然會在7種購買方案中選擇一種，因此我要在7種購買方案中選擇一個最佳情況。
   3、子問題是，我選擇了某個方案后，如何使得購買剩余的書能用最少的錢？并且這個選擇不會使得剩余的書為負數(shù)。母問題和子問題都是給定三卷書的購買量，求最少需要用的錢，所以有“子問題重疊”，問題中三個購買量設(shè)置為參數(shù)，分別為i、j、k。
   4、的確符合。
   5、邊界是一次購買就可以買完所有的書，處理方式請讀者自己考慮。
   6、每次選擇最多有7種方案，并且不會同時實施其中多種，因此方案的選擇互不影響，所以有“子問題獨立”。
   7、我可以用minMoney[j][k]來保存購買第1卷i本，第2卷j本，第3卷k本時所需的最少金錢。
   8、共有x * y * z 個問題，每個問題面對7種選擇，時間為：O( x * y * z * 7) =   O( x * y * z )。
   9、用函數(shù)MinMoney(i,j,k)來表示購買第1卷i本，第2卷j本，第3卷k本時所需的最少金錢，那么有：
           MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分別為對應的7種方案使用的最少金錢：
           s1 = 60 * 0.95 + MinMoney(i-1,j,k)
           s2 = 60 * 0.95 + MinMoney(i,j-1,k)
           s3 = 60 * 0.95 + MinMoney(i,j,k-1)
           s4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k)
           s5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
           s6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
           s7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1)