U238842 动态规划（DP）
题目背景
## 基本思想：穷举
### 特殊点：列出正确的状态转移方程才能有效穷举。
$1、$状态转移方程：每种情况与之前的情况的联系。
$2、$最优子结构：大问题化成小的子问题进行规划。
---
## 例题1：凑零钱
**题目：** 输入一个$n$，你有面值为$1、5、11$的纸币，问最少需要多少张可以付清？
---
### 代码
```cpp
#include
using namespace std;
int f[100005]; // 动态规划数组
int main(){
int n;
cin >> n;
for (int i = 1;i n;
for (int i = 1;i dp[i][j];
}
}
for (int i = n - 1;i >= 1;i--){
for (int j = 1;j n;
cin >> dp[0];
long long maxx = 0;
for (int i = 2;i > dp[i];
dp[i] = max(dp[i - 1] + dp[i],dp[i]);
if (dp[i] > maxx) maxx = dp[i];
}
cout
题目描述
## 例题4：传球游戏
**题目：**$n$个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意）。
求有多少种不同的传球方法可以使得从$1$号手里开始传的球，传了$m$次以后，又回到$1$号手里。
---
### 代码
```cpp
#include
using namespace std;
int main(){
int n,m,a[105][105] = {0};
cin >> n >> m;
a[0][1] = 1;
for (int i = 1;i
输入格式
## 区间DP
## [上课！](https://oi-wiki.org/dp/interval/)
```cpp
#include
using namespace std;
int n,j,dp[1005][1005] = {0},dp2[1005][1005] = {0},dp3[1005][1005] = {0};
int main(){
cin >> n;
for (int i = 1;i > dp[i][i];
dp[i + n][i + n] = dp[i][i];
}
for (int w = 2;w
输出格式
无