众所周知,在写 dp 问题时只要想出来状态表示和转移方程就能把一道题写的差不多了,所以在这里整理一下我写过的 dp 问题的解法,方便我后面举一反三
背包动态规划
线性动态规划
Luogu P1359 租用游艇 橙
题目链接
\(n\) 个点,从点 \(i\) 到点 \(j\) 的代价为 \(r_{i, j}\) 且任意 \(i,j\) 之间都存在 \(r_{i, j}\),求从点 \(1\) 到点 \(n\) 的最小代价。
\(f_i\) 为到点 \(i\) 的最小代价,则有:
\[f_i = \min_{j=1}^{j<=n-1}(f_{i-j}+r_{i,j})
\]
时间复杂度 \(O(n^2)\).