算法_动态规划

发表于2022-02-24更新于2025-09-28阅读次数

内容

动态规划适用的问题

求解最优化问题

解题过程

找到规模缩减的方案

经典题目

最长公共子序列

假设有X数组规模是m，Y数组规模是n，最长公共子序列为Z，规模为k(>=0)。

1
2
3
X={x1, x2, x3, ..., xm-1, xm};
Y={y1, y2, y3, ..., yn-1, yn};
Z={z1, z2, z3, ..., zk-1, zk};
1
2
3
4
5
6
1.若xm == xn, 则xm == yn == zk	//小写x，y，z表示某一字符
    则可以把问题的解规模解释为：Zk-1 = Xm-1 && Yn-1	//大写X,Y,Z表示数组规模问题
2.若xm != yn, xm != zk，
    则Zk = Xm-1 && Yn
3.若xm != yn, yn != zk，
    则Zk = Xm && Yn-1
1
2
3
4
5
c[m][n]表示MAXLEN
    c[m][n] = (m == 0 || n == 0) ? 0 : ...
    m > 1, n > 1
    c[m][n] = (xm == yn) ? c[m-1][n-1] + 1 : ...
    c[m][n] = (xm != yn) ? Max(c[m-1][n],c[m][n-1]) : ...

递归版本

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
#include<iostream>
#include<vector>
using namespace std;

int LCSLength(const char* X, int m, const char* Y, int n)
{
	if (m == 0 || n == 0)return 0;
	else
	{
		if (X[m] == Y[n])return LCSLength(X, m - 1, Y, n - 1) + 1;
		else
		{
			int max1 = LCSLength(X, m - 1, Y, n);
			int max2 = LCSLength(X, m, Y, n - 1);
			return max1 > max2 ? max1 : max2;
		}
	}
}
int main()
{
	char X[] = { "#ABCBDAB" };
	char Y[] = { "#BDCABA" };
	int xm = strlen(X) - 1;
	int yn = strlen(Y) - 1;
	vector<vector<int>> c;
	c.resize(xm + 1);
	for (int i = 0; i < xm + 1; ++i)
	{
		c[i].resize(yn + 1);
	}
	int maxlen = LCSLength(X, xm, Y, yn);
}

传入vector

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
#include<iostream>
#include<vector>
using namespace std;

int LCSLength(const char* X, int m, const char* Y, int n, vector<vector<int>> &c)
{
	if (m == 0 || n == 0)return 0;
	else
	{
		if (X[m] == Y[n])return LCSLength(X, m - 1, Y, n - 1) + 1;
		else
		{
			int max1 = LCSLength(X, m - 1, Y, n);
			int max2 = LCSLength(X, m, Y, n - 1);
			return max1 > max2 ? max1 : max2;
		}
	}
}
int main()
{
	char X[] = { "#ABCBDAB" };
	char Y[] = { "#BDCABA" };
	int xm = strlen(X) - 1;
	int yn = strlen(Y) - 1;
	vector<vector<int>> c;
	c.resize(xm + 1);
	for (int i = 0; i < xm + 1; ++i)
	{
		c[i].resize(yn+1, 0); //第二个参数代表每一个int都初始化为0
	}
	int maxlen = LCSLength(X, xm, Y, yn);
}

古典问题-兔子

有一对兔子，从出生后第3个月起，每个月都生一对兔子，小兔子长到第三个月开始每个月又生一对兔子，假如兔子不死，问第24个月的兔子总数为多少？

1
2
3
4
int dp[25];
dp[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
       1   1   2   3   5   
    发现，dp[i] = dp[i-1] + dp[i-2]