记录做过的的动态规划的题目
不定期更新
最长递增子序列
面试常考算法题(九)-经典动态规划1-牛客网
[编程题]最长递增子序列-牛客网
题目
对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2…，其中Ui < Ui+1，且A[Ui] < A[Ui+1]。
给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。
测试样例
[2,1,4,3,1,5,6],7
返回：4
解题思路
dp[i]记录长度为i的上升子序列的最后一个数中的最小值（可能有多个长度为i的上升子序列，我们只记录最后一个数最小的那个）
每次遍历的时候在dp[0,max]中找出第一个比A[i]大的数进行替换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public static int findLongest(int[] A,int n){
int[] dp = new int[n];
dp[0] = A[0];
int max = 0;
for(int i=0;i<n;i++){
int index = binarySearch(dp, 0, max, A[i]);
if(index<n){
dp[index] = A[i];
if(index>max)
max = index;
}
}
return max+1;
}
public static int binarySearch(int[] dp,int start,int end,int target){
if(start==end){
if(dp[start]>=target)
return start;
else
return start+1;
}
int mid = (start+end)/2;
if(dp[mid]>target){
if(mid==start)
return start;
return binarySearch(dp, start, mid-1, target);
}
else if(dp[mid]<target)
return binarySearch(dp, mid+1, end, target);
else
return mid;
}
public static void main(String args[]){
int[] A = {2,1,4,3,1,5,6};
System.out.println(findLongest(A, A.length));
}
|
最长公共子序列
面试常考算法题(九)-经典动态规划1-牛客网
[编程题]最长公共子序列-牛客网
题目
对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3…Un和V1,V2,V3…Vn,其中Ui<Ui+1，Vi<Vi+1。且A[Ui]== B[Vi]。
给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。
测试样例
“1A2C3D4B56”,10,”B1D23CA45B6A”,12
返回：6
解题思路
dp[i][j]代表子串A[0…i]和子串B[0…j]最长公共子序列的长度
如果A[i]==B[j],dp[i][j]=dp[i-1][j-1]
否则，dp[i][j]=max{dp[i][j-1],dp[i-1][j]}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public static int findLCS(String A, int n, String B, int m) {
int[][] dp = new int[n+1][m+1];
for(int i=0;i<=m;i++){
dp[0][i] = 0;
}
for(int i=0;i<=n;i++){
dp[i][0] = 0;
}
int max = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int tempMax = 0;
if(A.charAt(i-1)==B.charAt(j-1))
tempMax = dp[i-1][j-1]+1;
else
tempMax = Math.max(dp[i][j-1], dp[i-1][j]);
dp[i][j] = tempMax;
}
}
return dp[n][m];
}
public static void main(String args[]){
String A = "rsymsknwbiapzhuoeyhjubogitoqfkswhbqhwqzyjuvdlzjlhlaubecnkzgvurdsuvqghpjazgxvue";
String B = "sclzdzbtrrkdybusjyjrszzqaebkpdtqnqadndvkenqirqqsplmceuuzhukcxxnkcyyvucqjlkysfarxkulpayvtwfmfaqpikzdslpklomafvtesecxygahwnyljldutzsoywiwkugerfbfefcqfvcrzcvbevufzbkbhfeshhdasqo";
System.out.println(findLCS(A, A.length(), B, B.length()));
}
|
最长公共子串
面试常考算法题(九)-经典动态规划1-牛客网
[编程题]最长公共子串-牛客网
题目
对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,…Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。
给定两个字符串A和B，同时给定两串的长度n和m。
测试样例
“1AB2345CD”,9,”12345EF”,7
返回：4
解题思路
dp[i][j]代表以A[i-1]和B[j-1]为结尾的公共子串的最长长度（若A[i-1]!=B[j-1],dp[i][j]==0）
如果A[i-1]==B[i-1]&&A[i-2]==B[i-2], dp[i][j] == dp[i-1][j-1] + 1
如果A[i-1]==B[i-1], dp[i][j] = 1
如果A[i-1]!=B[i-1], dp[i][j] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| public static int findLongest(String A, int n, String B, int m) {
int[][] dp = new int[n+1][m+1];
for(int i=0;i<=n;i++){
dp[i][0] = 0;
}
for(int i=0;i<=m;i++){
dp[0][i] = 0;
}
int max = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(A.charAt(i-1)==B.charAt(j-1)){
if(i-2>=0 && j-2>=0 && A.charAt(i-2)==B.charAt(j-2))
dp[i][j] = dp[i-1][j-1] + 1;
else{
dp[i][j] = 1;
}
if(dp[i][j]>max)
max = dp[i][j];
}
else{
dp[i][j] = 0;
}
}
}
return max;
}
public static void main(String args[]){
String A = "12345CC1235";
String B = "12345B12345";
System.out.println(findLongest(A, A.length(), B, B.length()));
}
|
最小编辑代价
面试常考算法题(九)-经典动态规划1-牛客网
[编程题]最小编辑代价-牛客网
题目
对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。
给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。
测试样例
“abc”,3,”adc”,3,5,3,100
返回：8
解题思路
dp[i][j]代表子串A[0…i-1]变为子串B[0,,,j-1]的最小编辑距离
当A==”” 或者B==””时，cost是删除或插入的代价
当A!=”” 且 B!= “”时
A[i-1] == B[j-1] D[i][j] = D[i-1][j-1]
A[i-1] != B[j-1] D[i][j] = MIN{D[i-1][j-1]+c2(修改一个值)，D[i-1][j]+c1(删除一个值)，D[i][j-1]+c0(插入一个值)}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public static int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
int[][] dp = new int[n+1][m+1];
for(int i=1;i<=n;i++){
dp[i][0] = dp[i-1][0] + c1;
}
for(int i=1;i<=m;i++){
dp[0][i] = dp[0][i-1] + c0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(A.charAt(i-1)==B.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}
else{
dp[i][j] = Math.min(Math.min(dp[i-1][j]+c1, dp[i][j-1]+c0), dp[i-1][j-1]+c2);
}
}
}
return dp[n][m];
}
public static void main(String args[]){
String A = "abc";
String B = "adc";
Object o;
System.out.println(findMinCost(A, A.length(), B, B.length(), 5, 3, 100));
}
|
纸牌博弈
面试常考算法题(十)-经典动态规划2-牛客网
[编程题]纸牌博弈-牛客网
题目
有一个整型数组A，代表数值不同的纸牌排成一条线。玩家a和玩家b依次拿走每张纸牌，规定玩家a先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家a和玩家b都绝顶聪明，他们总会采用最优策略。
给定纸牌序列A及序列的大小n，请返回最后分数较高者得分数(相同则返回任意一个分数)。保证A中的元素均小于等于1000。且A的大小小于等于300。
测试样例
[1,2,100,4],4
返回：101
解题思路
dp[i][j]代表最优的情况，如果j-i+1是偶数，dp[i][j]代表的是先手的最优情况，如果j-i+1是奇数，dp[i][j]代表的是后手的最优情况
dp[i][j] = Math.max(A[i]+sum[i+1][j]-dp[i+1][j], A[j]+sum[i][j-1]-dp[i][j-1])，sum[i][j]代表A[i]到A[j]的总和
比如，dp[0][3]，如果拿A[0],那么在拿A[0]的情况下的最优结果是A[0]+sum[1][3]-dp[1][3] (dp[1][3]是另外一个人的最优情况)
同理拿A[3]的最优结果是A[3]+sum[0][2]-dp[0][2]，所以dp[0][3]的最优情况就是这两个最优结果中更优的一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| public static int cardGame(int[] A, int n) {
int[][] dp = new int[n][n];
int max = 0;
int[] sum = new int[n+1];
for(int i=1;i<=n;i++) {
sum[i] = sum[i-1] + A[i-1];
}
for(int r=1;r<=n;r++){
System.out.println("r:"+r);
for(int i=0;i<n-r+1;i++){
int j = i+r-1;
if(i==j)
dp[i][j] = A[i];
else
dp[i][j] = Math.max(A[i]+(sum[j+1]-sum[i+1])-dp[i+1][j], A[j]+(sum[j]-sum[i])-dp[i][j-1]);
System.out.println("i:"+i+" j:"+j+" "+dp[i][j]);
if(dp[i][j]>max)
max = dp[i][j];
}
}
return Math.max(dp[0][n-1], sum[n]-dp[0][n-1]);
}
public static void main(String args[]){
int[] A = {19,11,45,45,43,0,77,78,86,50,40,12,35,26,35,3,58,24,63,79,23,59,8,64,99,68,35,28,61,72,54,30,50,70,40,52,82,34,8,9,46,22,84,67,70,56,11,59,54,60,97,38,0,90,81,44,75,76,74,86,73,90,53,70,56,92,50,84,95,9,6,50,39,32,14,93,1,72};
System.out.println(cardGame(A, A.length));
}
|
随机的机器人
2017年校招全国统一模拟笔试(第四场)编程题集合-牛客网
[编程题]随机的机器人-牛客网
题目
有一条无限长的纸带,分割成一系列的格子,最开始所有格子初始是白色。现在在一个格子上放上一个萌萌的机器人(放上的这个格子也会被染红),机器人一旦走到某个格子上,就会把这个格子涂成红色。现在给出一个整数n,机器人现在会在纸带上走n步。每一步,机器人都会向左或者向右走一个格子,两种情况概率相等。机器人做出的所有随机选择都是独立的。现在需要计算出最后纸带上红色格子的期望值。
输入描述
输入包括一个整数n(0 ≤ n ≤ 500),即机器人行走的步数。
输出描述
输出一个实数,表示红色格子的期望个数,保留一位小数。
输入例子
4
输出例子
3.4
解题思路
dp[i%2][j][k]表示走了i步之后恰好有j个红色格子,并且此时机器人正好站在第k个红色格子上的概率。
最后求一个可能的状态的带权和就是所求期望
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| public static void main(String args[]){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
double[][][] dp = new double[2][n+3][n+3];
dp[0][1][0] = 1;
for(int i=1;i<=n;i++){
int cur = i%2;
int old = 1 - (i%2);
for(int j=1;j<=i+1;j++){
for(int k=0;k<j;k++){
dp[cur][j][k] = 0;
}
}
for(int j=1;j<=i+1;j++){
for(int k=0;k<j;k++){
int pos1 = j;
int pos2 = k+1;
if(pos1==pos2)
pos1++;
dp[cur][pos1][pos2] += dp[old][j][k]*0.5;
pos1 = j;
pos2 = k-1;
if(pos2==-1){
pos1++;
pos2++;
}
dp[cur][pos1][pos2] += dp[old][j][k]*0.5;
}
}
}
double reslut = 0;
for(int i=1;i<=n+1;i++){
for(int j=0;j<i;j++){
reslut += i*dp[n%2][i][j];
}
}
System.out.println(String.format("%.1f", reslut));
}
|
逃离农场
2017年校招全国统一模拟笔试(第四场)编程题集合-牛客网
[编程题]逃离农场-牛客网
题目
牛牛在农场饲养了n只奶牛,依次编号为0到n-1,牛牛的好朋友羊羊帮牛牛照看着农场.有一天羊羊看到农场中逃走了k只奶牛,但是他只会告诉牛牛逃走的k只奶牛的编号之和能被n整除。你现在需要帮牛牛计算有多少种不同的逃走的奶牛群。因为结果可能很大,输出结果对1,000,000,007取模。
例如n = 7 k = 4:
7只奶牛依次编号为0到6, 逃走了4只
编号和为7的有:{0, 1, 2, 4}
编号和为14的有:{0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6},{2, 3, 4, 5}
4只牛的编号和不会大于18,所以输出5.
输入描述
输入包括一行,两个整数n和k(1 ≤ n ≤ 1000),(1 ≤ k ≤ 50),以空格分割。
输出描述
输出一个整数表示题设所求的种数。
输入例子
7 4
输出例子
5
解题思路
dp[i][k][sum]表示前i个奶牛中选取k个他们的编号和对n取模为sum的方案数
dp[i][k][sum] = dp[i - 1][k][sum] + dp[i - 1][k - 1][(sum - i + n) % n]
然后可以滚动优化或者压缩一维空间。
压缩一维空间的道理就好像01背包问题的优化一样，每一次只用到前一次的值，第二层循环变成是递减的就可以使到，在计算dp[j][sum]的时候可以用到前一次的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void main(String args[]){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[][] dp = new int[51][1005];
int mod = 1000000007;
dp[0][0] = 1;
for(int i=1;i<=n;i++){
for(int j=k;j>0;j--){
for(int x=0;x<n;x++){
dp[j][x] = (dp[j][x] + dp[j-1][(x-i+n)%n])%mod;
}
}
}
System.out.println(dp[k][0]);
}
|
