1.背包问题

1.1递归

1.1.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
33
34
35
/*
w[]  物品的重量
c[]  物品的价值
index 物品的数量（下标）
capacity 背包的容量
*/

const int maxn = 1000;
int w[maxn], c[maxn], dp[maxn];
int solve(int w[], int c[], int index, int capacity) {
  	//基准条件：如果索引无效或者容量不足，直接返回当前价值0
    if (index < 0 || capacity <= 0) return 0;
  	//不放第index个物品所得价值
    int res = solve(w, c, index - 1, capacity);
  	//放第index个物品所得价值（前提是：第index个物品可以放得下）
    if (w[index] <= capacity) {
        res = max(res, c[index] + solve(w, c, index - 1, capacity - w[index]));
    }
    return res;
}


int main() {
    int n, capacity;
    scanf("%d%d", &n, &capacity);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    int x = solve(w, c, n, capacity);
    cout << "x=" << x << endl;
    return 0;
}

1.1.2记忆化搜索递归

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
const int maxn = 1000;
int w[maxn], c[maxn], dp[maxn];
int memo[maxn][maxn];
int solve(int w[], int c[], int index, int capacity) {
  	//基准条件：如果索引无效或者容量不足，直接返回当前价值0
    if (index < 0 || capacity <= 0) return 0;
  	//不放第index个物品所得价值
    int res = solve(w, c, index - 1, capacity);
  	//如果此子问题已经求解过，则直接返回上次求解的结果
    if (memo[index][capacity] != 0) {
        return memo[index][capacity];
    }
  	//放第index个物品所得价值（前提是：第index个物品可以放得下）
    if (w[index] <= capacity) {
        res = max(res, c[index] + solve(w, c, index - 1, capacity - w[index]));
    }
  	//添加子问题的解，便于下次直接使用
    memo[index][capacity] = res;
    return res;
}

int main() {
    int n, capacity;
    scanf("%d%d", &n, &capacity);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    int x = solve(w, c, n, capacity);
    cout << "x=" << x << endl;
    return 0;
}

1.2.动态规划算法

1.2.1下标从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
33
34
35
const int maxn = 100;
int w[maxn] = { 0 }, c[maxn] = { 0 }, dp[maxn] = { 0 };
int main() {
    int n, capacity;
    scanf("%d%d", &n, &capacity);
    //vector<vector<int> > a(n + 1, vector<int>(capacity + 1));
    int a[30][30] = {0};
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j < w[i]) {
                a[i][j] = a[i - 1][j];
            }
            else {
                a[i][j] = max(a[i - 1][j], a[i - 1][j - w[i]] + c[i]);
            }
            
        }
    }
    int max = a[1][1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (a[i][j] > max) {
                max = a[i][j];
            }
        }
    }
    printf("max=%d\n", max);
    return 0;
}

1.2.2下标从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
38
39
40
41
42
43
44
const int maxn = 100;
int w[maxn] = { 0 }, c[maxn] = { 0 }, dp[maxn] = { 0 };
int main() {
    int n, capacity;
    scanf("%d%d", &n, &capacity);
    vector<vector<int> > a(n + 1, vector<int>(capacity + 1));
    //int a[30][30] = {0};
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);
    }
    for (int i = 0; i <= capacity; i++) {
        if (w[0] < i) {
            a[0][i] = c[0];
        }
        else {
            a[0][i] = 0;
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (j < w[i]) {
                a[i][j] = a[i - 1][j];
            }
            else {
                a[i][j] = max(a[i - 1][j], a[i - 1][j - w[i]] + c[i]);
            }
            
        }
    }
    int max = a[0][0];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (a[i][j] > max) {
                max = a[i][j];
            }
        }
    }
    printf("max=%d\n", max);
    return 0;
}

1.3.深度优先搜索

1.3.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
const int maxn = 30;
int n, V, maxvalue = 0; //物品件数n，背包容量V，最大价值maxvalue
int w[maxn], c[maxn];   //w[i]为每件物品的重量，c[i]为每件物品的价值
//DFS,index为当前处理物品的编号
//sumw和sumc为当前总重量和当前总价值
void DFS(int index, int sumw, int sumc) {
    if (index == n) {   //已经完成对n件物品的选择(死胡同)
        if (sumw <= V && sumc > maxvalue) {
            maxvalue = sumc;    //不超过背包容量时更新背包的最大价值
        }
        retusrn;
    }
    //岔道口
    DFS(index + 1, sumw, sumc);     //不选第index件物品
    DFS(index + 1, sumw + w[index], sumc + c[index]);       //选择第index件物品
}
int main()
{
    scanf("%d%d", &n, &V);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);     //每件物品的重量
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);     //每件物品的价值
    }
    DFS(0, 0, 0);
    printf("%d\n", maxvalue);
    return 0;
}

1.3.2优化时间复杂度(剪枝)

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
const int maxn = 30;
int n, V, maxvalue = 0; //物品件数n，背包容量V，最大价值maxvalue
int w[maxn], c[maxn];   //w[i]为每件物品的重量，c[i]为每件物品的价值
//DFS,index为当前处理物品的编号
//sumw和sumc为当前总重量和当前总价值ji
void DFS(int index, int sumw, int sumc) {
    if (index == n) {   //已经完成对n件物品的选择(死胡同)
        return;
    }
    DFS(index + 1, sumw, sumc);     //不选择第index件物品
    //只有加入第index件物品后未超过物品的容量V，才能继续
    if (sumw + w[index] <= V) {
        if (sumc + c[index] > maxvalue) {
            maxvalue = sumc + c[index];     //更新最大价值
        }
        DFS(index + 1, sumw + w[index], sumc + c[index]);       //选择第index件物品
    }

}
int main()
{
    scanf("%d%d", &n, &V);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);     //每件物品的重量
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);     //每件物品的价值
    }
    DFS(0, 0, 0);
    printf("%d\n", maxvalue);
    return 0;
}

2.贪心算法

2.1.活动选择问题

有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。

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
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200;
struct aa {
	int start;
	int end;
};
bool cmp(aa x, aa y) {
	return x.end < y.end;
}
void src(int n, aa s[], bool a[]) {
	a[1] = true;
	int j = 1;
	for (int i = 2; i <= n; i++) {
		if (s[i].start > s[j].end) {
			a[i] = true;
			j = i;
		}
		else {
			a[i] = false;
		}
	}
}
int main() {
	int n;
	aa s[maxn];
	bool a[maxn] = { false };
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i].start;
	}
	for (int i = 1; i <= n; i++) {
		cin >> s[i].end;
	}
	sort(s + 1, s + 1 + n, cmp);
	src(n, s, a);
	cout << endl;
	for (int i = 1; i <= n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

2.2.最优装载问题

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。(意思就是在不超过载重量的情况下最多能装多少)

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 300;
int main()
{
	int weigh[maxn];		//集装箱重量的数组
	int num;		//定义集装箱的总数
	int max;		//定义船的最大载重量
	int result[maxn];		//定义可装载集装箱的数组
	int sum = 0;
	int count = 1;		//计数器
	cout << "请输入船的最大载重量" << endl;
	cin >> max;
	cout << "请输入集装箱的数量" << endl;
	cin >> num;
	cout << "请输入每个集装箱的重量" << endl;
	for (int i = 1; i <= num; i++) {
		cin >> weigh[i];
	}
	sort(weigh + 1, weigh + 1 + num);
	for (int i = 1; i <= num; i++) {
		sum = sum + weigh[i];
		if (sum <= max) {
			result[count] = weigh[i];
			count++;
		}
		else {
			break;
		}
	}
	cout << "可装载货物的重量分别为:" << endl;
	for (int i = 1; i < count; i++) {
		cout << result[i] << " ";
	}
	cout << endl;
	return 0;
}

3.递归与分治问题

3.1.n皇后问题

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

3.1.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
33
34
35
36
#include <iostream>
using namespace std;
const int maxn = 100;
int count1 = 0;
int n, p[maxn], hashtable[maxn] = { false };
void generatep(int index) {
	if (index == n + 1) {
		bool flag = true;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (abs(i - j) == abs(p[i] - p[j])) {
					flag = false;
				}
			}
		
		if (flag) {
			count1++;
		}
		return;
	}
	for (int x = 1; x <= n; x++) {
		if (hashtable[x] == false) {
			p[index] = x;
			hashtable[x] = true;
			generatep(index + 1);
			hashtable[x] = false;
		}
	}
}

int main() {
	cout << "请输入棋盘的行列数" << endl;
	cin >> n;
	generatep(1);
	cout << count1 << endl;
}

3.1.2回溯法

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
#include <iostream>
using namespace std;
const int maxn = 100;
int count1 = 0;
int n, p[maxn], hashtable[maxn] = { false };
void generatep(int index) {
	if (index == n + 1) {
		count1++;
		return;
	}
	for (int x = 1; x <= n; x++) {
		if (hashtable[x] == false) {
			bool flag = true;
			for (int pre = 1; pre < index; pre++) {
				if (abs(index - pre) == abs(x - p[pre])) {
					flag = false;
					break;
				}
			}
			if (flag) {
				p[index] = x;
				hashtable[x] = true;
				generatep(index + 1);
				hashtable[x] = false;
			}
		}
	}
}

int main() {
	cout << "请输入棋盘的行列数" << endl;
	cin >> n;
	generatep(1);
	cout << count1 << endl;
}

3.2.二分搜索

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
#include <iostream>

int binarysearch(int a[], int left, int right, int x) {
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (a[mid] == x) {
			return mid;
		}
		else if (a[mid] > x) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	return -1;
}
int main()
{
	int x;
	int a[8] = { 0,5,7,1,4,2,7,4 };
	//quicksort(a, 0, 7);
	/*bubblesort(a, 8);
	for (int i = 0; i < 8; i++) {
		cout << a[i] << " ";
	}*/
	x = binarysearch(a, 0, 7, 1);
	cout << x << endl;
	cout << endl;
}

3.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>  
using namespace std;  
int tile=1;                   //L型骨牌的编号(递增)  
int board[100][100];  //棋盘  
/***************************************************** 
* 递归方式实现棋盘覆盖算法 
* 输入参数： 
* tr--当前棋盘左上角的行号 
* tc--当前棋盘左上角的列号 
* dr--当前特殊方格所在的行号 
* dc--当前特殊方格所在的列号 
* size：当前棋盘的:2^k 
*****************************************************/  
void chessBoard ( int tr, int tc, int dr, int dc, int size )  
{  
    if ( size==1 )    //棋盘方格大小为1,说明递归到最里层  
        return;  
    int t=tile++;     //每次递增1  
    int s=size/2;    //棋盘中间的行、列号(相等的)  
    //检查特殊方块是否在左上角子棋盘中  
    if ( dr<tr+s && dc<tc+s )              //在  
        chessBoard ( tr, tc, dr, dc, s );  
    else         //不在，将该子棋盘右下角的方块视为特殊方块  
    {  
        board[tr+s-1][tc+s-1]=t;  
        chessBoard ( tr, tc, tr+s-1, tc+s-1, s );  
    }  
    //检查特殊方块是否在右上角子棋盘中  
    if ( dr<tr+s && dc>=tc+s )               //在  
        chessBoard ( tr, tc+s, dr, dc, s );  
    else          //不在，将该子棋盘左下角的方块视为特殊方块  
    {  
        board[tr+s-1][tc+s]=t;  
        chessBoard ( tr, tc+s, tr+s-1, tc+s, s );  
    }  
    //检查特殊方块是否在左下角子棋盘中  
    if ( dr>=tr+s && dc<tc+s )              //在  
        chessBoard ( tr+s, tc, dr, dc, s );  
    else            //不在，将该子棋盘右上角的方块视为特殊方块  
    {  
        board[tr+s][tc+s-1]=t;  
        chessBoard ( tr+s, tc, tr+s, tc+s-1, s );  
    }  
    //检查特殊方块是否在右下角子棋盘中  
    if ( dr>=tr+s && dc>=tc+s )                //在  
        chessBoard ( tr+s, tc+s, dr, dc, s );  
    else         //不在，将该子棋盘左上角的方块视为特殊方块  
    {  
        board[tr+s][tc+s]=t;  
        chessBoard ( tr+s, tc+s, tr+s, tc+s, s );  
    }  
}  
  
void main()  
{  
    int size;  
    cout<<"输入棋盘的size(大小必须是2的n次幂): ";  
    cin>>size;  
    int index_x,index_y;  
    cout<<"输入特殊方格位置的坐标: ";  
    cin>>index_x>>index_y;  
    chessBoard ( 0,0,index_x,index_y,size );  
    for ( int i=0; i<size; i++ )  
    {  
        for ( int j=0; j<size; j++ )  
            cout<<board[i][j]<<'/t';  
        cout<<endl;  
    }  
}

3.4.循环赛日程表

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
52
53
54
#include <iostream>
using namespace std;
#define N 50
//打印盒子 
void print(int n, int game[][N]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << game[i][j] << '\t';
        }
        cout << endl;
    }
}
//递归函数 
void arrange(int p, int q, int t, int arr[][N]) {
    //规格为4及以上，它的左上角和右上角要递归
    if (t >= 4) {
        arrange(p, q, t / 2, arr);
        arrange(p, q + t / 2, t / 2, arr);
    }
    //填左下角
    for (int i = p + t / 2; i < p + t; i++) {
        for (int j = q; j < q + t / 2; j++) {
            arr[i][j] = arr[i - t / 2][j + t / 2];
        }
    }
    //填右下角 
    for (int i = p + t / 2; i < p + t; i++) {
        for (int j = q + t / 2; j < q + t; j++) {
            arr[i][j] = arr[i - t / 2][j - t / 2];
        }
    }
}
//主函数
int main() {
    int n;
    int game[N][N];
    cout << "请输入选手人数:" << endl;
    cin >> n;
    //初始化第一行,其他全为0 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0)
                game[i][j] = j + 1;
            else
                game[i][j] = 0;
        }
    }
    //递归 
    arrange(0, 0, n, game);
    //打印输出循环赛日程表 
    print(n, game);
    system("pause");
    return 0;
}

3.5.马拦过河卒

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
#include<iostream>
using namespace std;
int total;  //记录路径总数
int end_r,end_c;  //记录B点
int hourse_r,hourse_c;  //记录马所在位置
int wayr[2]={1,0},wayc[2]={0,1};  //用于移动卒
int territory[9][2]={{0,0},{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};  //协助标记马的控制范围
bool map[20][20];  //用于标记马的控制范围
bool check(int x,int y)  //判断是否出界
{
	if(x>end_r||y>end_c) return 0;
	return 1;
}
void dfs(int r,int c)
{
	for(int i=0;i<2;i++)
		if(check(r+wayr[i],c+wayc[i])&&!map[r+wayr[i]][c+wayc[i]])  //判断能否到达该点，即是否出界或者被马占领
		{
			r+=wayr[i];  //移动行
			c+=wayc[i];  //移动列
			if(r==end_r&&c==end_c) total++;  //若到达B点，计数
			else dfs(r,c);  //递归调用，继续搜索
			r-=wayr[i];  //回溯
			c-=wayc[i];  //回溯
		}
}
int main()
{
	cin>>end_r>>end_c>>hourse_r>>hourse_c;
	for(int i=0;i<9;i++)   //标记马的控制范围
		map[hourse_r+territory[i][0]][hourse_c+territory[i][1]]=1;
	dfs(0,0);  //开始回溯
	cout<<total;  //输出结果
}

4,动态规划

4.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
using namespace std;
const int N = 100;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)//初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)//r个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
		{
			j = i + r - 1;
			m[i][j] = m[i][i]+m[i + 1][j] + A[i - 1] * A[i] * A[j];
			s[i][j] = i;
			for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
				if (t < m[i][j])//如果变换后的位置更优，则替换原来的分隔方法。
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}
void print(int i, int j)
{
	if (i == j)
	{
		cout << "A[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);//递归1到s[1][j]
	cout << ")";
}
int main()
{
	int n;//n个矩阵
	cin >> n;
	int i, j;
	for (i = 0; i <= n; i++)
	{
		cin >> A[i];
	}
	MatrixChain(n);
	cout << "最佳添加括号的方式为：";
	print(1, n);
	cout << "\n最小计算量的值为：" << m[1][n] << endl;
	return 0;
}

4.2.最长公共子序列

给定两个字符串（或数字序列）A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）

eg：字符串”sadstory”和”adminsorry”的最长公共子序列为”adsory”,长度为6

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 100;
char a[maxn], b[maxn];
int dp[maxn][maxn];
int main()
{
	int n;
	gets_s(a + 1, maxn);
	gets_s(b + 1, maxn);
	int lena = strlen(a + 1);
	int lenb = strlen(b + 1);
	for (int i = 0; i <= lena; i++) {
		dp[i][0] = 0;
	}
	for (int j = 0; j <= lenb; j++) {
		dp[0][j] = 0;
	}
	for (int i = 1; i <= lena; i++) {
		for (int j = 1; j <= lenb; j++) {
			if (a[i] == b[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	cout << dp[lena][lenb] << endl;
}

4.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
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100;
int main()
{
	int n;
	int f[maxn][maxn], dp[maxn][maxn];
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> f[i][j];
		}
	}
	for (int j = 1; j <= n; j++) {
		dp[n][j] = f[n][j];
	}
	for (int i = n - 1; i >= 1; i--) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
		}
	}
	cout << dp[1][1] << endl;
	return 0;
}

4.4.最大连续子序列和

给定一个数字序列A1,A2,…..,An,求i，j(1<=i<=j<=n),使得Ai+…+Aj最大，输出这个最大和

eg:-2 11 -4 13 -5 -2 显然最大和为20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100;
int src[maxn];
int dp[maxn];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> src[i];
	}
	dp[0] = src[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(src[i], dp[i - 1] + src[i]);
	}
	int k = 0;
	for (int i = 1; i < n; i++) {
		if (dp[i] > dp[k]) {
			k = i;
		}
	}
	cout << dp[k] << endl;
}

5.常见排序

5.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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100;
void selectsort(int a[], int n) {
	for (int i = 0; i < n; i++) {
		int k = i;
		for (int j = i; j < n; j++) {
			if (a[j] < a[k]) {
				k = j;
			}
		}
		swap(a[i], a[k]);
	}
}
int main()
{
	int a[maxn] = { 3,5,1,7,9,0,3,5 };
	selectsort(a, 8);
	for (int i = 0; i < 8; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

5.2.插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100;
void insertsort(int a[], int n) {
	for (int i = 1; i < n; i++) {
		int temp = a[i], j = i;
		while (j > 0 && temp < a[j - 1]) {
			a[j] = a[j - 1];
			j--;
		}
		a[j] = temp;
	}
}
int main()
{
	int a[maxn] = { 3,5,1,7,9,0,3,5 };
	insertsort(a, 8);
	for (int i = 0; i < 8; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

5.3.冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
void bubblesort(int a[], int n) {
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			if (a[j] > a[j + 1]) {
				swap(a[j], a[j + 1]);
			}
		}
	}
}
int main()
{
	int a[8] = { 0,5,7,1,4,2,7,4 };
	bubblesort(a, 8);
	for (int i = 0; i < 8; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

5.4.快速排序

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
#include <iostream>
#include <algorithm>
using namespace std;
int partition(int a[], int left, int right) {
	int temp = a[left];
	while (left < right) {
		while (left < right && a[right] > temp) right--;
		a[left] = a[right];
		while (left < right && a[left] <= temp) left++;
		a[right] = a[left];
	}
	a[left] = temp;
	return left;
}
void quicksort(int a[], int left, int right) {
	if (left < right) {
		int pos = partition(a, left, right);
		quicksort(a, left, pos - 1);
		quicksort(a, pos + 1, right);
	}
}
int main()
{
	int a[8] = { 0,5,7,1,4,2,7,4 };
	quicksort(a, 0, 7);
	for (int i = 0; i <
       8; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

5.5.归并排序

5.5.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
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100;
void merge(int a[], int l1, int r1, int l2, int r2) {
	int i = l1, j = l2;
	int temp[maxn], index = 0;
	while (i <= r1 && j <= r2) {
		if (a[i] <= a[j]) {
			temp[index++] = a[i++];
		}
		else {
			temp[index++] = a[j++];
		}
	}
	while (i <= r1) temp[index++] = a[i++];
	while (j <= r2) temp[index++] = a[j++];
	for (i = 0; i < index; i++) {
		a[l1 + i] = temp[i];
	}
}
void mergesort(int a[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergesort(a, left, mid);
		mergesort(a, mid + 1, right);
		merge(a, left, mid, mid + 1, right);
	}
}
int main()
{
	int a[maxn] = { 3,5,1,7,9,0,3,4 };
	mergesort(a, 0, 7);
	for (int i = 0; i < 8; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

5.5.2非递归实现

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100;
void merge(int a[], int l1, int r1, int l2, int r2) {
	int i = l1, j = l2;
	int temp[maxn], index = 0;
	while (i <= r1 && j <= r2) {
		if (a[i] <= a[j]) {
			temp[index++] = a[i++];
		}
		else {
			temp[index++] = a[j++];
		}
	}
	while (i <= r1) temp[index++] = a[i++];
	while (j <= r2) temp[index++] = a[j++];
	for (i = 0; i < index; i++) {
		a[l1 + i] = temp[i];
	}
}
void mergesort2(int a[], int n) {
	for (int step = 2; step / 2 <= n; step *= 2) {
		for (int i = 0; i < n; i += step) {
			int mid = i + step / 2 - 1;
			if (mid + 1 < n) {
				merge(a, i, mid, mid + 1, min(i + step - 1, n));
			}
		}
	}
}
int main()
{
	int a[maxn] = { 3,5,1,7,9,0,3,4 };
	mergesort2(a, 7);
	for (int i = 0; i < 8; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}