众所周知，在写 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)\).