C語言 深入探究動(dòng)態(tài)規(guī)劃之區(qū)間DP
寫在前面
之前講過背包問題，線性DP不知道大家忘了嗎，這次是區(qū)間DP
石子合并
題意：
合并 N 堆石子，每次只能合并相鄰的兩堆石子，求最小代價(jià)
解題思路：
關(guān)鍵點(diǎn)：最后一次合并一定是左邊連續(xù)的一部分和右邊連續(xù)的一部分進(jìn)行合并
狀態(tài)表示：f[i][j]表示將 i 到 j 這一段石子合并成一堆的方案的集合，屬性 Min
狀態(tài)計(jì)算： （1） i<j 時(shí)，f[i][j]=min f[i][k]+f[k+1][j]+s[j]−s[i−1] （2）i=j 時(shí)，
f[i][i]=0（合并一堆石子代價(jià)為 0）
問題答案： f[1][n]
所有的區(qū)間dp問題枚舉時(shí)，第一維通常是枚舉區(qū)間長度，并且一般 len = 1 時(shí)用來初始化，枚舉從 len = 2 開始；第二維枚舉起點(diǎn) i （右端點(diǎn) j 自動(dòng)獲得，j = i + len - 1）
模板代碼如下：
for (int len = 1; len <= n; len++) { // 區(qū)間長度
for (int i = 1; i + len - 1 <= n; i++) { // 枚舉起點(diǎn)
int j = i + len - 1; // 區(qū)間終點(diǎn)
if (len == 1) {
dp[i][j] = 初始值
continue;
}
for (int k = i; k < j; k++) { // 枚舉分割點(diǎn)，構(gòu)造狀態(tài)轉(zhuǎn)移方程
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
}
}
最后總的代碼：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 307;
int a[N], s[N];
int f[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
s[i] += s[i - 1] + a[i];
}
memset(f, 0x3f, sizeof f);
// 區(qū)間 DP 枚舉套路：長度+左端點(diǎn)
for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素個(gè)數(shù)
for (int i = 1; i + len - 1 <= n; i ++) {
int j = i + len - 1; // 自動(dòng)得到右端點(diǎn)
if (len == 1) {
f[i][j] = 0; // 邊界初始化
continue;
}
for (int k = i; k <= j - 1; k ++) { // 必須滿足k + 1 <= j
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
到此這篇關(guān)于C語言 深入探究動(dòng)態(tài)規(guī)劃之區(qū)間DP的文章就介紹到這了,更多相關(guān)C語言 區(qū)間DP內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在C++中把字符串轉(zhuǎn)換為整數(shù)的兩種簡單方法
經(jīng)常會(huì)遇到類型轉(zhuǎn)換，本文主要介紹了C++中把字符串轉(zhuǎn)換為整數(shù)的兩種簡單方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
C語言關(guān)于注釋的知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家分享的是關(guān)于C語言關(guān)于注釋的知識(shí)點(diǎn)總結(jié)，需要的朋友們可以參考學(xué)習(xí)下。2020-02-02
詳解C++中vector的理解以及模擬實(shí)現(xiàn)
vector是表示可變大小數(shù)組的序列容器。這篇文章主要為大家詳細(xì)介紹了vector的理解以及模擬實(shí)現(xiàn)，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下2023-03-03
C語言實(shí)現(xiàn)撲克牌計(jì)算24點(diǎn)
這篇文章主要為大家詳細(xì)介紹了C語言如何實(shí)現(xiàn)撲克牌計(jì)算24點(diǎn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
這篇文章主要介紹了C++中命名空間的概念及使用詳解,使用命名空間的目的是對(duì)標(biāo)識(shí)符的名稱進(jìn)行本地化，以避免命名沖突或名字污染，namespace關(guān)鍵字就是針對(duì)這種問題而出現(xiàn)的,需要的朋友可以參考下2023-08-08
C++實(shí)現(xiàn)希爾排序（ShellSort）
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)希爾排序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
本文給大家分享的是一個(gè)使用C語言開發(fā)的命令行下的簡易版掃雷小游戲，本身沒有什么太多的技術(shù)含量，只不過是筆者的處女作，所以還是推薦給大家，希望對(duì)大家學(xué)習(xí)C能夠有所幫助。2015-12-12
C++結(jié)構(gòu)體作為函數(shù)參數(shù)傳參的實(shí)例代碼
這篇文章主要介紹了C++結(jié)構(gòu)體作為函數(shù)參數(shù)傳參的實(shí)例代碼,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
楊輝三角形，又稱帕斯卡三角形、賈憲三角形、海亞姆三角形，它的排列形如三角形。本文將為大家介紹通過C++/C語言實(shí)現(xiàn)打印楊輝三角形的示例代碼，需要的可以參考一下2023-02-02
關(guān)于C++中由于字節(jié)對(duì)齊引起內(nèi)存問題定位分析
前幾天遇到一個(gè)稀奇古怪的問題，在創(chuàng)建對(duì)象的時(shí)候程序異常退出，查找代碼發(fā)現(xiàn)結(jié)構(gòu)體數(shù)組問題，最終把問題簡化得到解決方法，下面小編把我的問題及解決方案分享到腳本之家平臺(tái)供大家參考下2021-06-06