DP-動態規劃問題心得

05-27

DP-動態規劃問題心得

學習DP問題也有近一個月了，從初次接觸01背包問題，到花了幾天思考，最後恍然大悟，再陸續到後面的LCS，完全背包，等一系列變種的DP問題，越了解心中的佩服之情越盛，感嘆邏輯之美以及，真的只能承認，智商的差距，有時真的遙不可及。

步入正題，選了一道最簡單的DP問題來練手，儘管非常簡單，但沒想到真正AC下來，還是出乎意料的花了很久。

****************************我是分割線**************************

問題描述

　　媽媽給小B買了N塊糖！但是她不允許小B直接吃掉。
　　假設當前有M塊糖，小B每次可以拿P塊糖，其中P是M的一個不大於根號下M的質因數。這時，媽媽就會在小B拿了P塊糖以後再從糖堆里拿走P塊糖。然後小B就可以接著拿糖。
　　現在小B希望知道最多可以拿多少糖。

輸入格式

　　一個整數N

輸出格式

　　最多可以拿多少糖

樣例輸入

樣例輸出

數據規模和約定

　　N <= 100000

**********************************************************************

心得：

1.審題仔細，等到完全理解清楚題意，再去思考

2.思路理清楚，邏輯弄明白，再動手寫代碼

3.寫完以後盡量做一些簡單的優化一下（能更深層次的優化更好）

解題思路：

這道題關鍵在於數字P，首先理解數字P，它有三個條件，其一是質數，其二是M的一個因數，其三要小於根號下M。

接下來看問題，問的是 希望知道最多可以拿多少糖，而拿糖呢是 有N顆糖拿最多的糖 看到這個熟悉的架構了嗎，這表明，從N中拿最多的糖建立在從N-1到1中拿最多的糖的解上，而我們知道，動態規劃問題的一個要點在於，整體的最優解，一定建立或包含在子最優解上的，也就說從M中挑選P的最優解，一定建立在從M＇中挑選P＇的最優解上。通俗的講，假設有N = 15，我現在已經知道了N = 1 ，2 ，3 。。。14的答案，首先當N = 15時，它的質因數為2或者3.也就是說，我如果拿2顆，那麼還剩15 - 2 * 2 = 11顆，而我已經知道了11顆糖的時候我能拿的最多糖果的答案，那麼N = 15時，我能拿到的糖果就是當糖果還有11顆是我能拿的數量加上我已經拿的2顆。同理，還要考慮質因數為3的情況，兩種情況中那個情況最優，則答案就是那個。

所以我們可以得出遞推式：

dp[i] = dp[i - 2 * prime] + prime

其中，i代表當前的糖果數量，dp[i]的值為當糖果數量為I時我能拿的最多的糖果。

當然，我們這個遞推式還不完整，還漏了一點。就是會有多個質因數可以供選擇，我們必須對於每個質因數都計算一次，然後選其中最大的情況，所以，完善後的遞推式為

dp[i] = max( dp[i] , dp[i - 2 * prime] + prime )

當所有準備工作完成後，我們可以開始了

接下來放代碼:

#include <iostream>#include <vector>#include <cmath>using std::cout;using std::cin;using std::vector;using std::max;int main(){ vector<int> prime; //存放小於等於根號下 number 的所有質數 int number; //等待輸入的總糖果數量 bool flag; //狀態。判斷一個數字是不是質數 cin>>number; vector<int> dp(number + 1,0); //dp向量。記錄當糖果數量為i時能拿的糖果 //求質數，並將所有質數保存到prime中 int sqt1 = sqrt(number); for(int i = 2; i <= sqt1; ++i) { int sqt2 = sqrt(i); flag = true; for(int j = 2; j <= sqt2; ++j) { if(i % j == 0) flag = false; } if(flag == true) prime.push_back(i); } //處理dp向量 for(int i = 1; i != number + 1; ++i) //i代表dp的下標，代表糖果的數量 { int sqt2 = sqrt(i); int _size = prime.size(); for(int j = 0; j != _size; ++j) //遍歷整個質數的數組 { if(prime[j] <= sqt2 && i % prime[j] == 0) //如果這個質數小於等於根號下當前糖果的數量且是它的因數的話 { dp[i] = max(dp[i],dp[i - 2 * prime[j]] + prime[j]); //求最優解 } } } cout<<dp[number]; return 0;}