目錄
動(dòng)態(tài)規(guī)劃怎么學(xué)？
1. 題目解析
2. 算法原理
1. 狀態(tài)表示
2. 狀態(tài)轉(zhuǎn)移方程
3. 初始化
4. 填表順序
5. 返回值
3. 代碼編寫
寫在最后：
動(dòng)態(tài)規(guī)劃怎么學(xué)？
學(xué)習(xí)一個(gè)算法沒有捷徑，更何況是學(xué)習(xí)動(dòng)態(tài)規(guī)劃，
跟我一起刷動(dòng)態(tài)規(guī)劃算法題，一起學(xué)會(huì)動(dòng)態(tài)規(guī)劃！
1. 題目解析
題目鏈接：213. 打家劫舍 II - 力扣（Leetcode）
?這道題目也不難理解，
他和打家劫舍第一個(gè)版本只有一個(gè)差別，就是他的首尾是相連的，
其他的條件都是一致的。
那我們其實(shí)可以分析一下，我們能把這道題目轉(zhuǎn)換成打家劫舍第一個(gè)版本嗎？
如果我們偷0位置，那1位置就不能偷，那我們的2~n-2位置，就能為所欲為
如果我們不偷0位置，那我們1~n-1的位置就能為所欲為（轉(zhuǎn)換成打家劫舍I）
所以最后返回的值就是這兩種情況的最大值。
2. 算法原理
1. 狀態(tài)表示
?f [ i ] 表示偷到 i 位置時(shí)，偷 nums[ i ]，此時(shí)的最大金額
g [ i ] 表示偷到 i 位置時(shí)，不偷 nums[ i ]，此時(shí)的最大金額
2. 狀態(tài)轉(zhuǎn)移方程????????????????
根據(jù)我們的狀態(tài)表示，我們可以得出：
f [ i ] = g [ i -?1 ] + nums[ i ]
g [ i ] = max( f [ i - 1 ]，g [ i - 1 ]?)
3. 初始化
f [ 0 ] = num[ 0 ]， g [ 0 ] =?0
4. 填表順序
從左往右
5. 返回值
max(?f [ n - 1?]，g [ n - 1 ] )
3. 代碼編寫
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
return max(nums[0] + rob1(nums, 2, n - 2) , rob1(nums, 1, n - 1));
}
private:
int rob1(const vector<int>& nums, int start, int n) {
if(start > n) return 0;
int size = nums.size();
vector<int> f(size);
auto g = f;
f[start] = nums[start];
for(int i = start + 1; i <= n; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n], g[n]);
}
};寫在最后：
以上就是本篇文章的內(nèi)容了，感謝你的閱讀。
如果感到有所收獲的話可以給博主點(diǎn)一個(gè)贊哦。文章來源：http://www.zghlxwxcb.cn/news/detail-617937.html
如果文章內(nèi)容有遺漏或者錯(cuò)誤的地方歡迎私信博主或者在評(píng)論區(qū)指出~文章來源地址http://www.zghlxwxcb.cn/news/detail-617937.html
到了這里，關(guān)于【學(xué)會(huì)動(dòng)態(tài)規(guī)劃】打家劫舍 II（12）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
