线性规划

因为思路上是线性的，一行一行（列）的做，所以说是线性的

数字三角形

从最上层走到最下层，找到路径上的数加起来最大的路线

状态表示

走到(i, j)点的过程中，所有可能路径的最大值

状态计算

要分类看： 走到一个点，要么是从左上角来的，要么是从右上角来的，由此分为两类，按行和斜对角来计数

线性规划 2024-03-10 21.39.24.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Excalidraw Data

Text Elements

1

2， 3

7 4 8

10 9 6 5

Link to original

9(3,2) 2(2,1) 4(2,2) 走到9，必是从2，或4来的，走到9了要最大，即走到2或走到4时也是最大（因为9一定经过，要最大路径就得本来是最大路径） 即 f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j])

因为边缘的点可能没有左上或右上，所以要无效化这些路径

实现

//利用负无穷和max来将没有的路径无效化
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= i + 1; j ++)
            f[i][j] = -INF;
            
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];
    
    f[1][1] = a[1][1];
    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j]);
 
//遍历找底层最大值
    int ans = -INF;
    for(int i = 1; i <= n; i ++)
        ans = max(ans, f[n][i]);

上升子序列

上升子序列，方向是确定，从左到右的，是严格单调的递增序列，可以是离散的不同子序列

状态表示

到第i个数的上升序列中，最长的子序列的长度

状态计算

分类： 到第i个数的上升子序列的前一个数(倒数第二个数）分类，分为n类，每一类的最长上升子序列是 f[i] = max(f[1] + 1, f[2] + 1, f[3] + 1 …… f[i-1] + 1 条件是分类的数和第i个数构成上升关系

实现

for(int i = 1; i <= n; i ++)
{ 
	f[i] = 1;  //f[i]最小也是1
	for(int j = 1; j  <= n; j ++)
		if(a[i] > a[j])
			f[i] = max(f[j] + 1, f[i]);
}
    

int g[N];  //记录第i个数的最长子序列是从哪个数继承过来的
for(int i = 1; i <= n; i ++)
{
	f[i] = 1;
	for(int i = 1; i <= n; i ++)
	{
		if(a[i] > a[j])
		{
			if(f[i] < f[j] + 1)
			{
				f[i] = f[j] + 1;
				g[i] = j;
			}
		}
	}
	//逆序输出g
	int ans = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(f[i] > f[ans])
			ans = i;
	}
 
	for(int i = 0; i < f[ans]; i ++)
	{
		cout << a[ans];
		ans = g[ans];
	}
}

最长公共子序列

两个字符串中，最长的公共子序列

状态表示

遍历到第一串的 i 和第二串的 j 时，最长的公共子序列的长度

状态计算

分类：

• i 和 j 都不选的子序列
• i 选 j 不选的子序列
• j 选 i 不选的子序列
• i 和 j 都选的子序列

可以得到 f[i-1][j-1] f[i][j - 1] f[i - 1][j] f[i - 1][j - 1] + 1 其中，f[i][j - 1] f[i - 1][j]并不表示 i 一定选（j 一定选）的最长子序列，会包含都不选的情况，但没有都选的情况，二者的集合是有重叠的，但是不影响求最大值

实现

for(int i = 1; i <= n; i ++)
	for(int j = 1; j <= m; j ++)
	{
		//f[i][j]中，要么选了i进来，要么选了j进来，要么都不选
		//都不选包含在选了一个的最大值里面
		f[i][j] = max(f[i - 1][j], f[i][j - 1]);
		//要相等才可以都选
		if(a[i] == b[j])  f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
	}