dp
数字三角形
例题1:
题意:
从(1,1)到(r,c)摘花生,不可走回头路,最多可以摘多少
思路:
f[i, j]:(1,1)到(i,j)的最大摘花生数
核心代码:
for(int i = 1; i <= r; i++) { for(int j = 1; j <= c; j++) { f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]; } } cout << f[r][c] <<'\n';
例题2
题意:
从(1,1)到(n,n)在每一个方格中取数,方格中数被取后数变成0,可走两次,问可取最大数为几
思路:
用两次dp无法确定是否是最优解
用f[i1][j1][i2][j2]表示从(1,1)开始同时走分别走到(i1,j1)(i2,j2)的最大取数
i1+j1=i2+j2时才是同时走的
设k = i1+j1
用三维dp,f[k][i1][i2]求解(横纵坐标和为k时,纵坐标走的i1,i2的时候,最大取数)
核心代码:
for (int k = 2; k <= n + n; k ++ ) for (int i1 = 1; i1 <= n; i1 ++ ) for (int i2 = 1; i2 <= n; i2 ++ ) { int j1 = k - i1, j2 = k - i2; if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) { int t = w[i1][j1]; if (i1 != i2) t += w[i2][j2]; int &x = f[k][i1][i2]; x = max(x, f[k - 1][i1 - 1][i2 - 1] + t); x = max(x, f[k - 1][i1 - 1][i2] + t); x = max(x, f[k - 1][i1][i2 - 1] + t); x = max(x, f[k - 1][i1][i2] + t); } } printf("%d\n", f[n + n][n][n]);
最长上升子序列(LIS)
例题1
f[i] :所有以a[i]结尾的单调上升子序列长度最大值
核心代码:
for(int i = 1; i <= n; i++) { f[i] = 1; for(int j = 1; j < i; j++) { if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1); } } int ans = 0; for(int i = 1; i <= n; i++) { ans = max(ans, f[i]); } printf("%d", ans);
标签:i1,i2,j1,j2,int,动态,规划,AcWing From: https://www.cnblogs.com/lys-blogs123/p/17204676.html