物理

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

$\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]}$