? ? ? ? ?題目：強(qiáng)盜搶劫一排房間，每個(gè)房間都藏著一定數(shù)量的錢，不能搶劫兩個(gè)相鄰的房間，要求搶的錢最多

?????????數(shù)組如：[2,7,9,3,1]

?????????當(dāng)輸入的個(gè)數(shù)為0,1,2這個(gè)很好判斷，當(dāng)輸入的數(shù)字大于3時(shí)，就要用到動(dòng)態(tài)規(guī)劃了，方程是:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])，dp[i]是當(dāng)搶到第i個(gè)數(shù)時(shí)，能搶到最大值，其思路是，從局部最大值推到最終結(jié)果最大。假如當(dāng)我們搶到第5個(gè)房間，那這個(gè)第5個(gè)房間有二種情況，搶不和不被搶，因?yàn)橹荒芨粢粋€(gè)房間搶一個(gè)，如果這時(shí)候搶到第4個(gè)房間有個(gè)最大值，搶到第3個(gè)房間有個(gè)最大值，如果第3個(gè)房間的最大值加上這第5個(gè)房間的值大于搶到第4個(gè)房間時(shí)的最大時(shí)，那就搶3,5而不搶4，反而，就按搶4的策略，這樣從前往后推，最后的結(jié)果一定是最大的。
? ? ? ? ?

#include<iostream> #include<vector> using namespace std;class Solution { public:int rob(vector<int>& nums) {int size = nums.size();if (size == 0) return 0;if (size == 1) return nums[0];vector<int> dp(size, 0);dp[0] = nums[0];dp[1] = nums[0]>nums[1] ? nums[0] : nums[1];cout << "dp[0]=" << dp[0]<< endl;cout << "dp[1]=" << dp[1]<< endl;cout << "-----------------------" << endl;for (int i = 2; i < size; ++i){cout << "dp[i - 2]=" << dp[i - 2] << endl;cout << "nums[i]=" << nums[i] << endl;cout << "dp[i - 1]=" << dp[i - 1] << endl;dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);cout << "dp=" << dp[i] << endl;cout << "-----------------------" << endl;}return dp[size - 1];} };int main(){vector<int> v={2,7,9,3,1}; Solution s;int n = s.rob(v);cout<< "n=" << n << endl; }

? ?

dp[0]=2
????dp[1]=7
????-----------------------i=3時(shí)，能搶到的最大值是11
????dp[i - 2]=2
????nums[i]=9
????dp[i - 1]=7
????dp=11
????-----------------------i=4時(shí)，能搶到的最大值是11
????dp[i - 2]=7
????nums[i]=3
????dp[i - 1]=11
????dp=11
????-----------------------i=5時(shí)，能搶到的最大值是12
???dp[i - 2]=11?
???nums[i]=1
???dp[i - 1]=11
???dp=12
??-----------------------
???n=12

???每次用新房間的值加上dp里面存儲(chǔ)的值，在和上一個(gè)dp里面的值進(jìn)行比較,取其中較大的，這樣一直遞推下去。
?

參考地址：https://www.codeleading.com/article/400996440/

總結(jié)

以上是生活随笔為你收集整理的动态规划之强盗抢劫的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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