# A
f[i][j] 传 j 次到第i个人手里的方案数
转移方程：左边来，右边来
f[i][j] = f[i+1][j-1] +f[i-1][j-1]
初始化：f[1][0] =1 , f[2][1] =1,f[n][1]=1
先遍历 j 再遍历 i , 
环形， 1 的左边是n,n的右边是1(特判)

# B
- 跑步或者闪，休息
- 能闪就闪，不能闪的时候（1. 休息， 2. 跑步）
- 状态：f[i] 时间为 i 的时候能走的最远距离
```c++
#include <bits/stdc++.h>
using namespace std;
const int N  = 3e5 + 10;
int m, s, t;
int f[N];

int main() {
	cin >> m >> s >> t;
	// 能闪就闪现
	for (int i = 1; i <= t; i++) {
		if (m >= 10) {
			f[i] = f[i - 1] + 60;
			m -= 10;
		} else {
			f[i] = f[i - 1];
			m += 4;
		}
	}
	// 算跑， 当前这一秒是跑
	for (int i = 1; i <= t; i++) {
		f[i] = max(f[i - 1] + 17, f[i]);
		if (f[i] >= s) {
			cout << "Yes" << endl;
			cout << i;
			return 0;
		}
	}
	cout << "No" << endl;
	cout << f[t];
	return 0;
}

C

• n 本书，按高度排序，不整齐度为相邻两本书的宽度绝对值
• 求拿走 k 本书以后的最小不整齐度
• 状态： f[i][j] 前 i 本书留下 j 本的最小不整齐度，且满足 i 必须放置
• 放置的数的数量 n - k
• f[i][j] = min(f[i][j] , f[k][j-1]+abs(a[i] - a[k]))(k的范围:j-1到i)
• 初始化: memset(f, 0x3f, sizeof f); f[0][0] = 0; f[1][1] =0; f[i][1]=0

D

• N棵柿子树，每棵树上某个高度上有柿子
• 小猫跳的规则：1. 同一棵树，下滑， 2. 不同树，跳跃，下降 delta 个身位
• 求做多能吃多少个柿子
• 状态： f[i][j] 在第 i 棵树上，高度为 j ,最多柿子
• f[i][j] : 来源： 当前这颗树， 其他树
• f[i][j] = max(f[i][j+1] + a[i][j] , f[k][j+delta] + a[i][j])(k遍历1-n)
• 优化：
• f[k][j+delta] : 保证 f[i][j] 最大，要保证 f[k][j+delta] 最大
• 定义一个数组 maxx ， 去记录 maxx(当前高度下的f[i][高度]最大值)

E

• 低价购买，再低价购买
• 求最长下降子序列 加上 方案数
• if(f[i] == f[j]+1) cnt[i] += cnt[j]
• if(a[i]==a[j] &&f[i] == f[j]) f[i] = 0; // 实现去重

F

• f[i][j] : a 的前i个字符和b的前j个字符的最大相似度
• 匹配方式：插入一个（在 a中插入 ， b 中插入）， 直接匹配
• 直接匹配： f[i-1][j-1] + c[a[i]][b[j]]
• 在 a 中插入： f[i][j-1] + c[-][b[j]]
• 在 b 中插入： f[i-1][j] + c[a[i]][-]
• 初始化： f[i][0] = c[a[i]][-] f[0][j] = c[-][b[j]]

G

• 第一个棍子准备时间 1 分钟
• 下一个，如果 长和宽都小于上一个，没有准备时间
• 排序其中一个维度，剩下另一个维度就是最长上升子序列，
• 答案就是最长上升子序列的长度

H

• 字符串 a ,字符串 b，
• 扩展串，在其中加上空格
• 距离：相应位置上的 字符 的编码差值
• 求扩展串的最小距离
• f[i][j] 前i个字符和前j个字符的最大相似度
• 直接匹配：f[i-1][j-1] + abs(a[i] - b[j])
• 在 a 中插入空格：f[i][j-1] + k
• 在 b 中插入空格：f[i-1][j] + k
• 初始化： f[i][0] = f[i-1][0] +k , f[0][j] = f[0][j-1]+k

I

• 有很多任务，开始时间， 结束时间
• 选择其中一些任务执行，问做多能休息几分钟
• 无后效性: 当前确定了 i ,那就永久确定了，后续的选择不会影响当前的结果
• f[i]: 记录 从 i - n 时间内的最大能休息的时间
• f[i] = max(f[i] , f[k] ) (s - k 这个时间都在完成某个任务)

J

• n 本书，k 个人
• 每个人的抄写速度一样，求 n 个人写完 k 本书的最短时间
• 一个人只能连续抄写某一段的书，必须是连续
• 状态： f[i][j]: i个人抄写到j 的最短时间(最多的那个人抄写的总量最少)
• 时间 = 总的/速度， 速度一样， 最短时间(最多的那个人抄写的总量最少)
• 转移方程：
• f[i][j] : min( f[i][j] , max(f[i-1][k] , [k+1 , j]))
• [k+1 , j] 前缀和处理， sum[j] - sum[k]

K

• 看做多重背包， 每个物品的个数最多放 n 个
• 多重背包做，不能二进制优化，

L

• 星球分为开采(赚钱， 但是损耗设备)和维修(花钱，但是维护设备)
• 求最大收益
• 状态： f[i] 经过前i个星球的最大收益(错误)， 经过一个维修，肯定不维修？？？
• 前面的选择，会影响后面的选择，后面的会影响前面？？？
• 倒着来，
• 状态： f[i] ：经过 i - n 个星球的最大收益，倒着遍历
• 每个星球都经过，对于每个星球，无非就是要或者不要，在要或者不要中选最优的
• 资源型星球： 当前不要 f[i+1]

•         当前要  a[i].second + (1 - 0.01 * k) * f[i + 1]
  

• 维修型星球：不要： f[i+1]

•         要     -a[i].second + (1 + 0.01 * c) * f[i + 1]
  

• ans : f[1]*w

M

• 区间DP

N

• 完全背包求方案数
• 组合和排列
• 组合：先遍历物品，再遍历容量
• 排列：先遍历容量，再遍历物品
• f[0]=1
• f[j] +=f[j-a[i]]

O

• 把所有的全部弄成高度一致的
• 求你能弄成的最高高度是多少
• 对于每一个塔，一个积木只能用一次，01背包，
• 求能不能凑出高度为 i 的塔， mp[i] ++; // 高度为 i 的塔出现一次
• 对于所有的塔，高度都为同一个，求这个最高高度
• 找 mp[i] == t（城堡个数）, 且 i 最大，输出 i

P

• f[i][j] = max({f[i+1][j] ,f[i+1][j-1] , f[i+1][j+1]} )+ a[i][j];
• memset(f, 0xcf , sizeof f);
• f[n+1][m/2+1] = 0;
• max(f[1][i] (i：1-m))

Q

• 花费钱，时间，人品，
• 有确定的钱数，人品值
• 求最多的个数， 个数一样，求最少时间
• 01背包， 二维费用，钱和人品
• f1[费用][人品] ： 求在费用 和 人品下的最多数量
• f2[费用][人品]： 求在费用 和 人品下的最少时间
• if(f1[i-w[i]][j-v[i]]+1 == f1[i][j]) ( f2 = min(f2 , f2[i-w[i]][j-v[i]] +t[i]))

R

• 状态：f[i][j][t] 到达(i,j) 花费 时间 t 的方案数
• 状态转移：f[i][j][t] += f[x][y][t-1] (x,y 是 i,j 的上下左右方向)
• 初始化： f[r1][c1][0] = 1

S

• 状态： f[i][j][k] 到达(i,j) 的时候，花费了 k 个乘以 3 的机会
• 转移分为：左下角来不乘3，左下角来不乘3，右下角来不乘3，右下角来不乘3，
• f[i][j][k] = max(f[i+1][j][k-1] + a[i][j]*3 , f[i+1][j+1][k-1]+ a[i][j]*3 , f[i+1][j][k] , f[i+1][j+1][k]) 从下往上
• 结果：f[1][1][k]

T

• 状态：f[i]:到第 i 个为止的 组别数
• 转移： f[i] = min(f[k] + [k + 1, i]是否凑成一组)
• 难点： 判断 [k + 1, i] 能不能凑成一组 ？？？？
• 把 2 当成 -1 来做，求前缀和： abs(sum[i] - sum[k]) 就是代表人数差值
• 整个区间都是同一类人： abs(sum[i]-sum[k]) == i-k+1

u

• 01背包，求方案数
• 预先对数字进行排序(大的数字只能由比自己小的数字凑出来)

V

• 不超过 4 个数： 1 2 3 4
• f[i][j] 凑出 i 花费 j 个平方数的方案数
• ans = f[n][1]+f[n][2]+f[n][3]+f[n][4]
• f[j][k] += f[j-a[i]][k-1]

W

• 状态：f[i] 前 i 辆车通过桥的最短时间
• 转移： f[i] = min(f[j] + t[j+1,i]) ([j+1,i] 不能超重 ， 前缀和)
• t[j+1 , i] 预处理出 j+1 , i 之间的最短时间

X

• f[i][j] 以 (i,j) 为右下角的正方形的最大长度
• f[i][j] = 1 , 初始化
• 转移：f[i][j]=min{f[i][j-1],f[i-1][j],f[i-1][j-1]}+1 (前提：当前点和左边上边不等， 和左上角相等)
• res = max(1, f[i][j])

Y

• n 个50 ， n 个100

• f[i][j] 前 i 个人中有 j 张50的方案数

• f[i][j] 第i个人给的是 50，f[i-1][j-1]

• f[i][j] 第i个人给的是100，f[i-1][j+1]

• 初始化： f[0][0] =1

• ans :f[2*n][0]

• f[i][j] 用了 i 张 50 j 张100 的方案数

• f[i][j] = (f[i-1][j] +f[i][j-1])

• f[i][0] =1;

• ans:f[n][n]

Z

• 01 背包
• f[n] -1