物理

[信竞]动态规划题目讲解

$\Huge{\color{orange}{1.最大不相邻项和}}$

$\color{green}{问题：}$

给定一个长度为$n$的数组$a$，对于其中任意一个元素$a_i(a_i\geq 0)$,若选择了他，则与之相邻的元素不可被选择，求选出的元素最大的和

$\color{green}{状态定义：}$

$dp[i]$表示考虑到第$i$个元素$(1\leq i\leq n)$，所得的最大不相邻项之和

$\color{green}{状态初始化：}$

$dp[1]：$由于只有一个元素，故$dp[1]=a[1]$

$dp[2]：$由于不能选相邻元素，故$dp[2]=\max{a[1],a[2]}$

$\color{green}{状态转移：}$

对于$a[i](i\geq 3)$，都有选或不选两种可能性。

若选择，则$a[i -1]$不可被选择，此时的最大和为第$i$项加上前$(i-2)$项最大和，即$dp[i]=dp[i-2]+a[i]$

若不选择，则$a[i -1]$可以被选择，此时的最大和为$dp[i-1]$

综上所述，$dp[i]=\max{dp[i-2]+a[i],dp[i-1]}$

$\Huge{\color{orange}{2.最大连续子段和}}$

$\color{green}{问题：}$

给定一个长度为$n$的数组$a$，$a_i\in \mathbb{Z}$，选出其中任意连续的一段，不能不选，求段内所有元素之和的最大值

$\color{green}{状态定义：}$

$dp[i]$表示考虑到第$i$个元素$(1\leq i\leq n)$，所得的最大连续子段和

$\color{green}{状态初始化：}$

$dp[1]：$由于只有一个元素，又不能不选，故$dp[1]=a[1]$

$dp[2]：$要么只选第一个元素，要么只选第二个元素，要么都选，故$dp[2]=\max{a[1]+a[2],\max{a[1],a[2]}}$

$\color{green}{状态转移：}$

对于$a[i](i\geq 3)$，都有把它接入上一个连续子段和另外开一个新子段两种可能性。

若接入，则总和应该是$dp[i-1]+a[i]$即$dp[i]=dp[i-1]+a[i]$

若新开，则$dp[i]=a[i]$

综上所述，$dp[i]=\max{dp[i-1]+a[i],a[i]}$

对dp数组内的所有元素取最大值即可