---

tags:

• 算法
• DP
• 动态规划

---

大家觉得还可以可以点赞、收藏、关注一下吧！
也可以到我的个人博客参观一下，估计近几年都会一直更新！和我做个朋友吧！https://motongxue.cn

---

D2 坐标型动态规划

• 最简单的动态规划类型
• 给定一个序列或者网格

• 需要找到序列中某个/些子序列或网格中的某条路径
  • 某种性质最大/最小
  • 计数
  • 存在性
• 动态规划方程 f[i] 中的下标i表示以ai为结尾的满足条件的子序列的性质，f[i][j] 中下标 i , j 表示以格子( i , j )为结尾的满足条件的路径的性质
  • 最大值/最小值
  • 个数
  • 存在性
• 坐标型动态规划的初始条件f[0]就是指以a0为结尾的子序列的性质

Longest increasing continuous subsequence（序列型）

Problem

Give an integer array，find the longest increasing continuous subsequence in this array.

An increasing continuous subsequence:

• Can be from right to left or from left to right.
• Indices of the integers i0n the subsequence should be continuous.

Example

For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.

For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4.

public int LIS(int[] A,int n){int i,j;int[]  f = new int[n];int res = 0;for(i=0;i<n;i++){f[i]=1;if(i>0&&A[i]>A[i-1]){f[i] = f[i-1]+1;}res = Math.max(res,f[i]);}return res;
}
public int longestIncreasingContinuousSubsequence(int[] A){int n = A.length;if(n==0){return 0;}int r1 = LIS(A,n);//reverseint i,j,t;i=0;j= n-1;while(i<j){t=A[i];A[i] = A[j];A[j] = t;++i;--j;}int r2 = LIS(A,n);return r1>r2?r1:r2;}

Longest Increasing Subsequence

public class LongestIncreasingSubsequence {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}System.out.println(lis_NN(a));}}public static int lis_NN(int[] a) {// 时间复杂度为O(n*n)int n = a.length;int[] dp = new int[n];int[] pi = new int[n];int i, j, p = 0;for (i = 0; i < n; i++) {dp[i] = 1;// 初值置为1，代表长度至少为1// 初始化为1，长度最短为自身pi[i] = -1;}int max = 1;// 最大长度for (i = 1; i < n; i++) {for (j = 0; j < i; j++) {// 对i前每一个数字进行判断if (a[j] < a[i]) {// 若该i值dp[i] = Math.max(dp[j] + 1, dp[i]);// ！！！if (dp[j] + 1 == dp[i]) {pi[i] = j;// 记录选择}}}max = Math.max(dp[i], max);// 进行比较if (dp[i] == max) {// 这个判断是为了记录选择p = i;}}int[] seq = new int[max];for (i = max - 1; i >= 0; i--) {seq[i] = a[p];p = pi[p];}for (i = 0; i < max; i++) {System.out.print(seq[i]);}return max;}public static int lis_NlogN(int[] a) {//时间复杂度为O(n*logN)int n = a.length;int[] dp = new int[n + 1];//因为dp下标从1开始，故为长度n+1dp[1] = a[0];//默认至少有一个数字int index = 1;//dp的下标for (int i = 1; i < n; i++) {if (a[i] > dp[index]) {//若a[i]大于dp数组最大值，则直接添加dp[++index] = a[i];} else {//否则找到dp中第一个大于等于a[i]的位置，用a[i]替换之。int tempIndex = BinarySearch(dp, index, a[i]);//需自定义二分查找，否则找不到时会出现-1，数组越界dp[tempIndex] = a[i];}}return index;}// 二分查找变体 找到第一个大于n的位置indexprivate static int BinarySearch(int[] dp, int len, int n) {int left = 1;int right = len;while (right > left) {int mid = (left + right) / 2;if (dp[mid] == n) {return mid;} else if (dp[mid] < n) {left = mid + 1;} else {right = mid;//注意这里不能为right = mid -1;}}return right;}
}

Minimum Path Sum(坐标型)

Description

给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

你在同一时间只能向下或者向右移动一步

Example

样例 1:输入:  [[1,3,1],[1,5,1],[4,2,1]]输出: 7样例解释：路线为： 1 -> 3 -> 1 -> 1 -> 1。                                                 

解法一：

解法二：滚动数组（空间优化）

1. 对于网格上的动态规划，如果 f[i][j]只依赖于本行的f[i][x]与前一行的f[i-1][y]，那么就可以采用滚动数组的方法压缩空间。空间复杂度变为O(N)
2. 如果网格行数少，列数多，可以改为逐列计算。空间复杂度为O(M)

Bomb Enemy

题目：

Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.

Example:

For the given grid0 E 0 0
E 0 W E
0 E 0 0return 3.

思路：

分上下左右四个方向，定义四个数组

向上能炸死多少敌人：之前上面炸死的人，加上本格炸死的人

如果想打印每次决策的路径，则需要记录下每一次选择

传纸条

Problem

从左上传到右下，和从右下传到左上，同一个格子不能重复使用，求途径格子和最大值

可以看做两个左上传递到右下，枚举两个格子进行dp，还有个特性，就是两个格子的横轴坐标和相等

双线程DP（四维DP)
//双线程dp.....f[x1][y1][x2][y2]是当一次传纸条在(x1,y1)第二次在(x2,y2)时的最大值
int a1=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);
int a2=max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]);
dp[i][j][k][l]=max(a1,a2)+a[i][j]+a[k][l];
if(i==k && j==l) {dp[i][j][k][l]-=a[i][j];}
每次选择最大值，两个DP同时进行，如果有冲突的话，一个暂停一步（减去a[i] [j]或者是a[k] [l]），这样就错开了

#include <iostream>
using namespace std;
int dp[55][55][55][55]= {0};
int a[55][55]= {0};
int main()
{
//    freopen ("传纸条.in","r",stdin);int m,n;cin>>m>>n;for (int i=1; i<=m; i++) {for(int j=1; j<=n; j++) {cin>>a[i][j];}}for(int i=1; i<=m; i++) {for(int j=1; j<=n; j++) {for(int k=1; k<=m; k++) {for(int l=1; l<=n; l++) {int a1=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);int a2=max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]);dp[i][j][k][l]=max(a1,a2)+a[i][j]+a[k][l];if(i==k && j==l) {dp[i][j][k][l]-=a[i][j];}}}}}cout<<dp[m][n][m][n];
}

四维优化

if((i != a || j != b) && i+j == a+b)
{
// “&&”后面是关键，可以节约很多时间，以接近三维的速度dp[i][j][a][b] = max(dp[i-1][j][a-1][b],dp[i-1][j][a][b-1],dp[i][j-1][a-1][b],dp[i][j-1][a][b-1])+c[i][j]+c[a][b];dp[m][n][m][n] = max(dp[m-1][n][m-1][n],dp[m-1][n][m][n-1],dp[m][n-1][m-1][n],dp[m][n-1][m][n-1]);
}

三维DP

此题的多线程DP的状态转移方程是这样的

f[i][j][k]=max(f[i][j][k]，f[i-1][j][k-1],f[i-1][j-1][k],f[i-1][j-1][k-1],f[i-1][j][k])

f[i][j][k]表示,走到第i步，第一次去x坐标为j，第二次去x坐标为k的最优值，因为统计有总步数，所以第一次走的y值，第二次走的y值都可以推出来。所以就将维数降到了三维。然后三重循环就可以了。

public class Main {static int n, m;static int[][] a = new int[101][101];static int[][][] f = new int[400][101][101];public static void main(String[] args) {Scanner sc = new Scanner(System.in);m = sc.nextInt();n = sc.nextInt();for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)a[i][j] = sc.nextInt();for (int i = 2; i <= m + n - 1; i++)for (int j = 1; j <= Math.min(i, m); j++)for (int k = 1; k <= Math.min(i, m); k++) {f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j][k - 1]);f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - 1][k]);f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - 1][k - 1]);f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j][k]);if (k == j)f[i][j][k] += a[j][i - j + 1];if (k != j)f[i][j][k] += a[j][i - j + 1] + a[k][i - k + 1];}System.out.println(f[m + n - 1][m][m]);}}

三取方格数

描述

设有N*N的方格图，我们将其中的某些方格填入正整数，
而其他的方格中放入0。

某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。

在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。

输入格式

第一行:N (4<=N<=20)
接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0

输出格式

一行，表示最大的总和。

样例

Input
4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4
Output
39

#include<bits/stdc++.h>
using namespace std;
int a[25][25]={0},f[45][45][45][45]={0};
int main()
{  //代码看着比较难受，大家凑合着看吧ios :: sync_with_stdio(false);int n,m,t;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];m=2*n-2;f[0][1][1][1]=a[1][1];//赋边界值，不要忘了for(int s=1;s<=m;s++)//三条线路共同开始，循环步数for(int i=1;i<=n;i++)//第1条for(int j=1;j<=n;j++)//第2条for(int k=1;k<=n;k++)//第3条{if(i==j&&j==k)//三条线路重合的情况，一一列举t=a[i][s+2-i];//知道了行就能知道列，公式:步数+2-行数，大家可以试验一下else if(i==j)t=a[i][s+2-i]+a[k][s+2-k];else if(i==k)t=a[i][s+2-i]+a[j][s+2-j];else if(j==k)//两个点重合的情况t=a[j][s+2-j]+a[i][s+2-i];else //不重合的情况t=a[i][s+2-i]+a[j][s+2-j]+a[k][s+2-k];f[s][i][j][k]=max(f[s-1][i][j][k],max(f[s-1][i][j-1][k-1],max(f[s-1][i-1][j][k-1],max(f[s-1][i-1][j-1][k],max(f[s-1][i-1][j][k],max(f[s-1][i][j-1][k],max(f[s-1][i][j][k-1],f[s-1][i-1][j-1][k-1])))))))+t;}//到达三个点有八种方案，max（求当前最优解）cout<<f[m][n][n][n]<<endl;return 0;
}

位操作

题目： 求N的二进制中有多少个1

子问题： 求Y=(N>>1) 的二进制有多少个

知识点：

1. 和位操作相关的动态规划一般用值做状态
2. i & 1==0? 偶数 ：奇数

f[i]=f[i>>1]+(i % 2)

---

2020年7月9日更

---

大家觉得还可以可以点赞、收藏、关注一下吧！
也可以到我的个人博客参观一下，估计近几年都会一直更新！和我做个朋友吧！https://motongxue.cn