Wanjia Huang

西南交通大学 软件工程

0%

【笔记】算法分析与设计

发表于 更新于 分类于

​ 2021年算法分析与设计笔记，仅供参考。

算法分析与设计

递归与分治

1.基础

  1. 设计思想：

    • 平衡子问题：子问题的规模最好大致相同
    • 独立子问题：相互独立，不需要再去求解

  2. 求解过程：

    • 划分：将规模为n的原问题划分为k个规模较小的问题。
    • 求解子问题：递归/循环
    • 合并：将各个子问题的解合并起来

2.实例一：数字旋转方阵

​ image-20210509151332121

AC代码：

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
#include<iostream>
using namespace std;
int data2[20][20] = { 0 };
void full(int number, int begin, int size)
{
	int i, j, k;
	if (size == 0)return;
	if (size == 1) {
		data2[begin][begin] = number;
		return;
	}
	i = begin;
	j = begin;
	for (k = 0; k < size - 1; k++) {
		data2[i][j] = number;
		number++;
		i++;
	}
	for (k = 0; k < size - 1; k++) {
		data2[i][j] = number;
		number++;
		j++;
	}
	for (k = 0; k < size - 1; k++) {
		data2[i][j] = number;
		number++;
		i--;
	}
	for (k = 0; k < size - 1; k++) {
		data2[i][j] = number;
		number++;
		j--;
	}
	full(number, begin + 1, size - 2);
	return;
}
int main()
{
        full(0, 0, 6);
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++)
                cout << data2[i][j] << " ";
            cout << endl;
        }
}

3.实例二：棋盘填充

实验4.3

首先将该棋盘进行划分，将整个棋盘划分为大小相同且均包含一个特殊方格的子期盼，既将imgimg的棋盘划分为4块 imgimg的子棋盘。之后递归求解，递归地填充各个子棋盘，填充分为四个情况：

①如果特殊方块在左上角子棋盘，则递归填充左上角子棋盘；否则填充右上角棋盘，然后递归填充左上角子棋盘。

②如果特殊方块在右上角子棋盘，则递归填充右上角子棋盘；否则填充右上角子棋盘的左下角，将左下角看做黑色方块，然后递归填充右上子棋盘。

③如果特殊放开在左下角子棋盘，则递归填充左下角子棋盘；否则填充左下角子棋盘的右上角，将右上角看做黑色方块，然后递归填充左下子棋盘。

④如果特殊方块在右下角子棋盘，则递归填充右下子棋盘；否则填充右下角子棋盘的右下角，将左上角看做黑色方块，然后递归填充右下子棋盘。

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
void chessboard(int i, int j, int x	, int y, int size) {
	if(size==1)
        return;
    int size_now=size/2;
    int t=ncount++;
    int i_center=i+size_now;
    int j_center=j+size_now;
    if(x<i_center && y<j_center){
        chessboard(i,j,x,y,size_now);
    }
    else{
        chess[i_center-1][j_center-1]=t;
        chessboard(i,j,x,y,size_now);
    }
    if(x<i_center && y>=j_center){
        chessboard(i,j_center,x,y,size_now);
    }
    else{
        chess[i_center-1][j_center]=t;
        chessboard(i,j_center,i_center-1,j_center,size_now);
    }
    if(x>=i_center && y<j_center){
        chessboard(i_center,j,x,y,size_now);
    }
    else{
        chess[i_center][j_center-1]=t;
        chessboard(i_center,j,i_center,j_center-1,size_now);
    }
    if(x>=i_center && y>=j_center){
        chessboard(i_center,j_center,x,y,size_now);
    }
    else{
        chess[i_center][j_center]=t;
        chessboard(i_center,j_center,i_center,j_center,size_now);
    }
}

4.实例三：LeetCode题目53 最大子序列和（分治实现）

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000

提示：

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

官方图解

思路：维护三个方向的值。

AC代码：

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_N 20

int max3(int, int, int);
int maxSubArrayAns(int[]);
int maxSubArray(int[], int, int);

int main() {
	int nums[MAX_N];
	int i;
	srand(time(0));
	printf("array: \n");
	for (int i = 0; i < MAX_N; i++) {
		nums[i] = (int)(rand() % (MAX_N * 2) - MAX_N);
		printf("%d\t", nums[i]);
	}
	printf("\n");
	printf("The max subsequen sum is %d.\n", maxSubArrayAns(nums));


	return 0;
}

int max3(int a, int b, int c) {
	if (a > b)
		return a > c ? a : c;
	else
		return b > c ? b : c;
}

int maxSubArray(int nums[], int left, int right) {
	int maxLeftSum, maxRightSum;
	int maxLeftBorderSum, maxRightBorderSum;
	int leftBorderSum, rightBorderSum;

	if (left == right)
		if (nums[left] > 0)
			return nums[left];
		else
			return 0;

	int mid = (left + right) / 2, i;
	maxLeftSum = maxSubArray(nums, left, mid);
	maxRightSum = maxSubArray(nums, mid + 1, right);

	maxLeftBorderSum = 0, leftBorderSum = 0;
	for (i = mid; i >= left; i--) {
		leftBorderSum += nums[i];
		if (leftBorderSum > maxLeftBorderSum)
			maxLeftBorderSum = leftBorderSum;
	}

	maxRightBorderSum = 0, rightBorderSum = 0;
	for (i = mid + 1; i <= right; i++) {
		rightBorderSum += nums[i];
		if (rightBorderSum > maxRightBorderSum)
			maxRightBorderSum = rightBorderSum;
	}

	return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

int maxSubArrayAns(int nums[]) {
	return maxSubArray(nums, 0, MAX_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
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;
int sum;
int MaxSum(int a[], int left, int right)
{
	int center,i;
	int leftsum, rightsum;
	int s1 = 0, lefts = 0, s2 = 0, rights = 0;
	sum = 0;
	if (left == right)
	{
		if (a[left] > 0)sum = a[left];
		else sum = 0;
	}
	else
	{
		center = (left + right) / 2;
		leftsum = MaxSum(a, left, center);
		rightsum = MaxSum(a, center + 1, right);
		for (i = center; i >= left; i--)
		{
			lefts += a[i];
			if (lefts > s1)s1 = lefts;
		}
		for (i = center + 1; i <= right; i++)
		{
			rights += a[i];
			if (rights > s2)s2 = rights;
		}
		sum = s1 + s2;
		if (sum < leftsum)sum = leftsum;
		if (sum < rightsum)sum = rightsum;
	}
	return sum;
}

int main() {
	int a[6] = { -20,11,-4,13,-5,2 };
	cout << "max=" << MaxSum(a, 0, 5);
	return 0;
}

5.实例四：合并排序

img

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
void merge(int arr[], int low, int mid, int high)
{
	int i, k;
	int *tmp = (int *)malloc((high - low + 1) * sizeof(int));
	//申请空间，使其大小为两个
	int left_low = low;
	int left_high = mid;
	int right_low = mid + 1;
	int right_high = high;
	for (k = 0; left_low <= left_high && right_low <= right_high; k++) {  // 比较两个指针所指向的元素
		if (arr[left_low] <= arr[right_low]) {
			tmp[k] = arr[left_low++];
		}
		else {
			tmp[k] = arr[right_low++];
		}
	}
	if (left_low <= left_high) {  //若第一个序列有剩余，直接复制出来粘到合并序列尾
	//memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
		for (i = left_low; i <= left_high; i++)
			tmp[k++] = arr[i];
	}
	if (right_low <= right_high) {
		//若第二个序列有剩余，直接复制出来粘到合并序列尾
		//memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
		for (i = right_low; i <= right_high; i++)
			tmp[k++] = arr[i];
	}
	for (i = 0; i < high - low + 1; i++)
		arr[low + i] = tmp[i];
	free(tmp);
	return;
}
void merge_sort(int arr[], int first, int last) {
	int mid = 0;
	if (first < last) {
		mid = (first + last) / 2;
		merge_sort(arr, first, mid);
		merge_sort(arr, mid + 1, last);
		merge(arr, first, mid, last);
	}
	return;
}

image-20210509160911567

​ 有cn是因为归并算法的复杂度为cn

6.实例五：线性时间选择算法

输入：一个包含n个（不同的）数的集合A和一个数i，1<=i<=n。

输出：元素x属于A，它恰大于A中其他的i-1个元素。

算法思想：

我们知道，快速排序算法的一次排序的思想是:
 找到一个数字作为标准，把比该数小的放左边，比该数大的放右边

要找到第k小的元素，最粗暴的就是全部排序，但这样做了很多多余的工作,借鉴快速排序算法的一次排序思想，我们可以以数组首位元素作为一个标准，把小于它的放左边，大于它的放右边：

当这个标准左边的元素和它加起来为k的话，就找到第k小的数了
当这个标准左边的元素和它加起来小于k的话，就向右边继续找第（k-1-该数下标）小的数
当这个标准左边的元素和它加起来大于k的话，就向左边继续找第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
/*
	left 进行线性选择的首位下标
	right 进行线性选择的末尾下标
	k 寻找第k位小的元素
*/
int linearTimeSelection(int left, int right, int k) {
	if (left >= right) return a[left];
	int point = a[left];
	int i = left,
		j = right + 1;

	while (1) {
		do { i++; } while (a[i] < point);
		do { j--; } while (a[j] > point);
		if (i >= j) break;
		swap(a[i], a[j]);
	}

	if (j - left + 1 == k) return point;
	a[left] = a[j];
	a[j] = point;

	if (j - left + 1 < k) return linearTimeSelection(j + 1, right, k - (j + 1 - left));	//向右找
	return linearTimeSelection(left, j - 1, k);	//向左找
}

7.实例六：循环赛日程表

设有n=2^{k}个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：

（1）个选手必须与其他n-1个选手各赛一次；

（2）每个选手一天只能赛一次。

按此要求，可将比赛日程表设计成一个 n 行n-1列的二维表，其中，第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。

算法思想：

image-20210626193055862

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void GameTable(int k, int **a) {
	//n=2^k个选手参加比赛
	//先求解两个选手的比赛日程，得到左上角的元素
	int t,temp,n=2,i,j;
	a[1][1] = 1; a[1][2] = 2; a[2][1] = 2; a[2][2] = 1;
	for (t = 1; t < k; t++)
	{
		temp = n;
		n = n * 2;
		//左下角
		for (i = temp + 1; i <= n; i++)
			for (j = 1; j <= temp; j++)
				a[i][j] = a[i - temp][j] + temp;
		//右上角
		for (i = 1; i <= temp; i++)
			for (j = temp + 1; j <= n; j++)
				a[i][j] = a[i + temp][(j + temp) % n];
		//右下角
		for (i = temp + 1; i <= n; i++)
			for (j = temp + 1; j <= n; j++)
				a[i][j] = a[i - temp][j - temp];
	}
}

8.实例七：快速排序

算法思想：在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void quicksort(int a[],int left,int right)
{
    if (left<right) return;
    int base = a[left];
    int i=left,j=right;
    while(i<j){
        while(i<j && a[j]>=base)j--;
        while(i<j && a[i]<=base)i++;
        swap(a[i],a[j]);
    }
    a[left]=a[i];
    a[i]=base;
    quciksort(a,left,i-1);
    quicksort(a,i+1,right);
}

动态规划

1.基础

​ 动态规划分类：

​ ①自顶向下的备忘录法【这大部分要用到递归，不推荐】

​ ②自底向上的动态规划

​ 动态规划问题的性质：

①最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

②重叠子问题

在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次，在求cut（4）的时候cut（0）被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。

2.实例一：钢条切割问题

这里写图片描述

一、问题分析

长度为n英寸的钢条共有2n-1种不同的切割方案，因为在距离钢条左端i(i=1,2,…n)英寸处，总是可以选择切割或不切割。

如果一个最优解将钢条切割为k段（对某个img），那么最优切割方案img，将钢条切割为长度分别为i1,i2…ik的小段得到的最大收益为img。对于img，img。其中，pn对应不切割，对于每个i=1,2,…,n-1，首先将钢条切割为长度为i和n-i的两段，接着求解这两段的最优切割收益ri和rn-i(每种方案的最优收益为两段的最优收益之和)。当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。

钢条切割问题还存在一种相似的但更为简单的递归求解方法：将钢条从左边切割下长度为i的一段，只对右边剩下的长度为n-i的一段继续进行切割，对左边的一段则不再进行切割。这样得到的公式为：img。这样原问题的最优解只包含一个相关子问题（右端剩余部分）的解，而不是两个。

二、朴素的递归求解

AC代码，自顶向下

1
2
3
4
5
6
7
8
9
10
11
12
13
int CutRod(const int *p, int n)
{
    if(n==0)
        return 0;
    int q=-1;
    for(int i=1;i<=n;i++)
    {
        int tmp=p[i]+CutRod(p,n-1);
        if (q<tmp)
            q=tmp;
    }
    return q;
}

三、动态规划自底向上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int BottomUpCutRod(const int *p, int n)
{
    int *r = new int[n + 1];
    r[0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        int q = -1;
        for (int j = 1; j <= i; ++j)
        {
            int tmp = p[j] + r[i - j];
            q = q > tmp ? q : tmp;
        }
        r[i] = q;
    }

    return r[n];	//这个函数返回的是最优解的收益。
}

渐进运行时间img。

3.实例二：线性模型基础，过桥问题

线性模型的是动态规划中最常用的模型，上文讲到的钢条切割问题就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。【例题1】是一个经典的面试题，我们将它作为线性模型的敲门砖。

【例题1】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
每次过桥的时候最多两个人，如果桥这边还有人，那么还得回来一个人（送手电筒），也就是说N个人过桥的次数为2*N-3（倒推，当桥这边只剩两个人时只需要一次，三个人的情况为来回一次后加上两个人的情况…）。有一个人需要来回跑，将手电筒送回来（也许不是同一个人，realy？！）这个回来的时间是没办法省去的，并且回来的次数也是确定的，为N-2，如果是我，我会选择让跑的最快的人来干这件事情，但是我错了…如果总是跑得最快的人跑回来的话，那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了，花费的总时间：

T = minPTime * (N-2) + (totalSum-minPTime)

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19，但是实际答案应该是17。

具体步骤是这样的：

第一步：1和2过去，花费时间2，然后1回来（花费时间1）；

第二歩：3和4过去，花费时间10，然后2回来（花费时间2）；

第三部：1和2过去，花费时间2，总耗时17。

所以之前的贪心想法是不对的。我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以opt[i] = opt[i-1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以opt[i] = opt[i-2] + a[1] + a[i] + 2a[2] (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题)
所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2a[2] }

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
int lowTime(int F[], int n)
{
	vector<int> ans(n);
	ans[0] = 0;
	ans[1] = F[1];
	ans[2] = F[2];
	for (int i = 3; i <=n; i++)
	{
		ans[i] = min(ans[i - 1] + F[1] + F[i], ans[i - 2] + F[1] + F[i] + 2 * F[2]);
	}
	return ans[n - 1];
}

3.区间模型

区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。
【例题2】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。
典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，在X两边各添加一个字符’a’后，aXa仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：

1、在A[j]后面添加一个字符A[i]；

2、在A[i]前面添加一个字符A[j]；

根据两种决策列出状态转移方程为：

d[ i ] [ j ]= min{ d[ i +1 ] [ j ], d[ i +1 ] [ j -1] } + 1; (每次状态转移，区间长度增加1)
这里写图片描述

1
2
3
4
5
6
7
int dp(int i,int j){
    if(i>=j)return 0;
    int &ans=d[i][j];
    if(ans>=0)return ans;
    if(s[i]==s[j])return ans=dp(i+1,j-1);
    return ans=min(dp(i+1,j),dp(i,j-1))+1;
}

4.实例三：最大字段和（动态规划实现）

1
2
3
4
5
6
7
8
9
10
11
int maxsum(int *a,int n)
{
    int sum=0,b=0;
    for(int i=1;i<=n;i++)
    {
        if(b>0) b+=a[i];
        else	b=a[i];
        if (b>sum) sum=b;
    }
    return sum;
}

5.实例四：矩阵连乘

理解数学公式比较重要

矩阵连乘问题的定义
输入：n个矩阵A1,A2,…,An，其中Ai的维数为pi-1×pi
Ai 和Ai+1是可乘的

输出：连乘积A1A2A3…An

优化目标：最小计算代价（最优的计算次序）

矩阵乘法的代价：乘法次数
若A 是p ×q 矩阵，B 是q ×r 矩阵，则A ×B 的代价是pqr
因为矩阵乘法满足结合律，因此矩阵连乘可以由不同的计算次序，这种计算次序可以用加括号来表示。

1
2
3
矩阵乘法的代价：乘法次数
若A 是p ×q 矩阵，B 是q ×r 矩阵，则A ×B 的代价是pqr
因为矩阵乘法满足结合律，因此矩阵连乘可以由不同的计算次序，这种计算次序可以用加括号来表示。

三个矩阵A1: 10×100, A2: 100×5，A3: 5×50
(A1A2)A3
代价：10×100×5＋10×5×50＝7500
A1(A2A3)
代价：100×5×50＋10×100×50＝75000

可见不同的计算次序会导致不同的计算代价，我们要做的就是让这个代价最小。

我们自然可以用穷举法计算每次不同的结合次序带来的不同代价，然后取最小值，但是这样我们得到的复杂度将达到

分析最优解结构
将矩阵连乘积AiAi+1…Aj，记为A[i:j]

设AiAi+1…Aj的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开得到：(Ai… Ak) (Ak+1 …Aj)

总的计算量就是：A[i:k]的计算量＋A[k+1: j]的计算量+A[i:k]和A[k+1:j]相乘的计算量

建立的递归关系就是

计算A[i:j]所需的最小乘法次数为m（i，j）

其中Ai是Pi-1 x Pi的矩阵

其中Ai是Pi-1 x Pi的矩阵

接下来我们借助填表过程理解递归的过程，现在给出下列矩阵：

在这里插入图片描述

填表过程是按对角线填写的，只利用到了二维数组的右上角一部分。

根据递推公式，我们可以知道，在i=j时m=0，所以先构造出最长的对角线部分的数据，如下图：

在这里插入图片描述

现在我们继续构造，

1
2
3
m（1,2）=min{m[1][1]+m[2][2]+p0p1p2}={0+0+303515}=15750

m(2,3) = min(m[2][2]+m[3][3]+p1p2p3=0+0+35155）=2625

同理，后面不再一一列举；

再多说一点，有时我们会遇到有多个划分，我们取最小值就可以了，

1
例如：m（1,4）=min{m[1][2]+m[3][4]+p0p2p4 或者是 m[1][1]+m[2][4]+p0p1p4或者是m[1][3]+m[4][4]+p0p3p4}，其中的值已经在前面求出来了，这也是动态规划要记录所有值的原因。

结果图如下：读者可以自行计算验证。

在这里插入图片描述

那么，我们最后如何得知是哪个地方要加括号呢？
根据最后的公式。

例如，假设最后的m[1:6]=m[1,1]+m[2][6]+p0p2p6（笔者构造的，跟上面的例子没关系），那么我们就知道是（A1(A2A3A4A5A6)）,再看m[2:6],根据公式找退出括号位置，一直推到最后即可。

我们不难发现，加括号的位置其实就是k 的对应序号的矩阵，在写算法时我们就可以用另外的数组记录下对应位置的k值。在最后输出时把这个数组按逻辑输出。

最终这个算法的复杂度

在这里插入图片描述

AC代码：

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;
}

6.实例五：最长公共子序列

7.实例六：最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：.

输入：s = “cbbd”
输出：”bb”
示例 3：

输入：s = “a”
输出：”a”

算法思路：

该问题可以用dp做，属于区间模型。

image-20210627132342039

image-20210627132430763

AC代码：

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 <string>
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size();
		// dp[left][right]标记从i到j是否是字串
		vector<vector<int>> dp(n, vector<int>(n));
		string ans;
		// length表示判断的字串的长度
		// left表示字串的左边起始位置
		// right表示字串的右边起始位置
		//length 的计算公式为 j-i+1
		for (int length = 0; length < n; length++) {	//枚举子串长度
			for (int left = 0; left + length < n; left++) {	//枚举子串边界
				int right = left + length;
				// 即字符串长度为1时，矩阵对角线
				if (length == 0) dp[left][right] = true;
				// 字符串长度为2的时候，只需判断两者是否相等
				else if (length == 1) dp[left][right] = (s[left] == s[right]);
				else {  // 字符串长度大于等于3之后
					   // 其是否是回文串取决于当前left和right及更小一号的字符串
					   // 更新参考值为矩阵的左下方
					dp[left][right] = (s[left] == s[right] && dp[left + 1][right - 1]);
				}
				// 如果当前left位置到right位置的字串能够构成回文串，并且现在长度+1后大于之前记忆中的子回文串的长度，那么更新回文串！这里也可以优化成记录起始位置和长度的两个int，返回时再截取
				if (s[left]==s[right] && (length + 1 > ans.size())) {
					ans = s.substr(left, length + 1);
				}
			}
		}
		return ans;
	}
};

8.实例七：0/1背包问题

img

背包总容量为10，现在要从中选择物品装入背包中，要求物品的重量不能超过背包的容量，并且最后放在背包中物品的总价值最大。

题解：

a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积（重量）；

b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；

c) 约束条件，W1X1+W2X2+…+WnXn<capacity；

d) 定义 f(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；

e) 寻找递推关系式，面对当前商品有两种可能性：

　　　　第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即 f(i,j) = f(i-1,j)；

　　　　第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即f(i,j)=max｛ f(i-1,j)，f(i-1,j-w(i))+v(i) ｝

　　　　　　　其中f(i-1,j)表示不装，f(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

　　　　由此可以得出递推关系式：

　　　　1) j<w(i) f (i,j)=f (i-1,j)

　　　　2) j>=w(i) f (i,j)=max｛ f (i-1,j)，f (i-1,j-w(i))+v(i) ｝

样例的dp表：

img

这个图可能有点问题，样例是 2 4 3 7

AC代码：

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
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1001
#define W 1002
int dp[N][W];
int w[N];
int v[N];
int main()
{
	int n, ww;	//个数跟背包容量
	cin >> n >> ww;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 1; i <= n; i++) {
		//从行开始遍历，可选的物品数量以此递增
		for (int j = 1; j <= ww; j++) {
			//从列开始遍历，背包的重量依次递增
			if (j < w[i]) {
				//背包重量比本次所选物品还小
				dp[i][j] = dp[i - 1][j];	//还是等于上次
			}
			else {
				//状态方程  f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
		}
	}
   int j = ww;
    for(int i=n;i>0;i++){
        //x[i]返回路径
        if(dp[i][j]>dp[i-1][j]){
            x[i]=1;
            j=j-w[i];
        }
        else x[i]=0;
    }
	cout << dp[n][ww] << endl;
}

9.实例八：LeetCode62 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

image-20210627195550280

解题思路：

image-20210627195711803

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int uniquePaths(int m, int n){
    int dp[m][n];
    //状态方程：f(i,j)=max(f(i-1,j),f(i,j-1))
    //初始化dp
    for(int i=0;i<m;i++){
        dp[i][0]=1;
    }
    for(int i=0;i<n;i++){
        dp[0][i]=1;
    }
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

10. 模板，矩阵中的路径

1
2
3
4
5
6
7
8
9
10
网格中中的动态规划算法，其状态转移方程可以归纳为如下：

最短路径（带权值的网格）：dp[i][j] = min{dp[i - 1][j], dp[i][j - 1]} + grid[i][j]
所有路径（包含障碍，1表示障碍，0表示通行）：if grid[i][j] ==0 :dp[i][j] = dp[i - 1][j] + dp[i][j - 1],否则,dp[i][j] = 0
所有路径（不包含障碍）,状态方程同2中if，也可以直接返回组合数C(m+n)(m)，m，n为网格的行数和列数。
本题：一条路径，状态方程和1一样，只不过每个点的权值相等。
思路：我们可以通过状态方程1去递归求解一条路径（m + n），并且当grid[i][j] = 1时，令dp[i][j] = m + n + 1。最后我们只需要判断dp[m - 1][n - 1]是否等于m+n就可以知道是否存在一条路径，由于本题不仅仅需要考虑是否存在一条路径，还需要返回所经过的每一个点，因此我们需要一个记录每次状态转移来源的矩阵pos。在计算状态转移方程时，同时记录当前pos[i][j]为来源的点。最后我们从右下角进行溯源，从而找到所有路径上的所有点。

作者：lzx1997
链接：https://leetcode-cn.com/problems/robot-in-a-grid-lcci/solution/tong-yi-de-dpmo-ban-qiu-jie-ju-zhen-zhon-w3pg/

贪心算法

1. 分数背包问题

2. 单源最短路径(Dijkstra)

算法思想：

  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

void Dijkstra(int n,int v,int dist[],int prev[]){
	for(int i=1;i<=n;i++){
		dist[i]=c[v][i];//对dist数组进行初始化，从源点到i的距离：V->i 赋值给dist 
		s[i]=false;//将s数组置空 
		if(dist[i]==maxint)prev[i]=0;//判断V->i是否可以直达，如果可以直达的话，给prev数组赋值为其前一个节点 
		else prev[i]=v;
	}
	dist[v]=0;s[v]=true;//先将源点设为true，将其纳入s集合 
	for(int i=1;i<=n;i++){
		int temp=maxint;
		int u=v;
		for(int j=1;j<=n;j++){
			if((!s[j])&&(dist[j]<temp)){//找出除s集合外的，且路径最短的一个点 
				u=j;
				temp=dist[j];
			}
		}
		s[u]=true;//将本次循环新找到的点，纳入s集合中 
		for(int j=1;j<=n;j++){//将u作为源，更新dist数组中的数据 
			if((!s[j])&&(c[u][j]<maxint)){//j不在j集合中，且从u->j可以直达的点 
				int newdist = dist[u]+c[u][j]; 
				if(newdist<dist[j]){//若通过u->j的路线，比原来的路线要短，则更新dist数组中的数据 
					dist[j]=newdist; 
					prev[j]=u;
				}
			}
		}
		for(int k=1;k<=n;k++){
			cout<<dist[k]<<" ";
		}
		cout<<endl;
	}	
}

完整实现：

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
71
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int maxint=65535;
int c[6][6]={{0,0,0,0,0,0},{0,0,10,65535,30,100},{0,65535,0,50,65535,65535},{0,65535,65535,0,65535,10},{0,65535,65535,20,0,60},{0,65535,65535,65535,65535,0}};
bool s[6];
 
 
void Dijkstra(int n,int v,int dist[],int prev[]){
	for(int i=1;i<=n;i++){
		dist[i]=c[v][i];//对dist数组进行初始化，从源点到i的距离：V->i 赋值给dist 
		s[i]=false;//将s数组置空 
		if(dist[i]==maxint)prev[i]=0;//判断V->i是否可以直达，如果可以直达的话，给prev数组赋值为其前一个节点 
		else prev[i]=v;
	}
	dist[v]=0;s[v]=true;//先将源点设为true，将其纳入s集合 
	for(int i=1;i<=n;i++){
		int temp=maxint;
		int u=v;
		for(int j=1;j<=n;j++){
			if((!s[j])&&(dist[j]<temp)){//找出除s集合外的，且路径最短的一个点 
				u=j;
				temp=dist[j];
			}
		}
		s[u]=true;//将本次循环新找到的点，纳入s集合中 
		for(int j=1;j<=n;j++){//将u作为源，更新dist数组中的数据 
			if((!s[j])&&(c[u][j]<maxint)){//j不在j集合中，且从u->j可以直达的点 
				int newdist = dist[u]+c[u][j]; 
				if(newdist<dist[j]){//若通过u->j的路线，比原来的路线要短，则更新dist数组中的数据 
					dist[j]=newdist; 
					prev[j]=u;
				}
			}
		}
		for(int k=1;k<=n;k++){
			cout<<dist[k]<<" ";
		}
		cout<<endl;
	}	
}
void foundDist(int dist,int prev[]){
	int prevNode=prev[dist];
	vector<int> vec;
	vec.push_back(dist);
	vec.push_back(prevNode);
	while(prevNode!=1){
		prevNode=prev[prevNode];
		vec.push_back(prevNode);
	}
	cout<<"最短路径为：";
	for(int i=vec.size()-1;i>=0;i--){
		cout<<vec[i]<<" ";
	}
}
int main(){
	int distNum;
	int dist[6];
	int prev[6];
	cout<<"dist数组中的数据："<<endl; 
	Dijkstra(5,1,dist,prev);
	cout<<"prev数组中的数据："; 
	for(int i=1;i<=5;i++){
		cout<<prev[i]<<" ";
	}
	cout<<endl;
	cout<<"请输入终点：";
	scanf("%d",&distNum);
	foundDist(distNum,prev);
}

回溯与分支限界

1.基础

2.实例1：括号问题

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：

输入：n = 1
输出：[“()”]

题解：

如果去除题目中的“有效性”，只考虑组合，那么这个题就变得容易多了。也就是有 n 个 “(“ 和 n 个 “)”，有 2n 个格子，写出所有可能的组合。image.png

填入第1个空位后，需要考虑第2个空位需要填什么，
填入第2个空位后，需要考虑第3个空位需要填什么，
填入第3个空位后，需要考虑第4个空位需要填什么，
…

我们发现，存在相似性的子问题，那么使用递归可以解决。 在 2n 个格子填满的时候，递归终止。也就是上图中，在树的第 n 层递归终止。

上面的解法存在大量的无效括号组合，我们需要去除无效的组合，也就是剪掉不合法的分支。

image.png

不合法的分支如何判断呢？

某个空位置可以放左括号的条件是，左括号是由余量的，也就是使用的左括号数量 < n，或者说左括号的剩余量 > 0；
某个空位置可以放右括号的条件是，已经使用的左括号的数量大于右括号的数量，或者说右括号的剩余量大于左括号的剩余量；

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> ans;
    vector<string> generateParenthesis(int n) {
        recursion( n, n, 2 * n, "");
        return ans;
    }

    void recursion(int left, int right, int level, string str)
    {
        if(level == 0) {
            ans.push_back(str);
            return ;
        }
        if(left > 0)
        //left>0的话表明左边括号还有余量，继续向左子树发展结点
            recursion(left -1, right, level - 1,  str + "(");
        //右边子树还有余量
        if(right > left)
            recursion(left, right - 1, level - 1, str + ")");
    }
};

3.实例2：LeetCode39组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

1
2
3
4
5
6
7
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题解：

朴素的回溯法

我们定义递归函数 dfs(target, combine, idx) 表示当前在 candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine。递归的终止条件为 target <= 0 或者 candidates 数组被全部用完。那么在当前的函数中，每次我们可以选择跳过不用第 idx 个数，即执行 **dfs(target, combine, idx + 1)**。也可以选择使用第 idx 个数，即执行 dfs(target - candidates[idx], combine, idx)，注意到每个数字可以被无限制重复选取，因此搜索的下标仍为 idx。

心得：

题目这种无限递归，然后依靠达到限界条件return的做法，可以适用于这些组合问题

AC代码：

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
class Solution {
public:
	void dfs(vector<int>&candidates, vector<vector<int>> &ans, vector<int> &combine, int target, int index) {
		if (index == candidates.size()) return;   //index是层数，也就是当前备选集里面的元素个数
		if (target == 0) {
			ans.emplace_back(combine); //combine相当于temp
			return;
		}
		//这里就直接跳过了
		dfs(candidates, ans, combine, target, index + 1);
		//
		if (target - candidates[index] >= 0) {
			combine.emplace_back(candidates[index]);
			//选candidates[index]
			dfs(candidates, ans, combine, target - candidates[index], index);
			combine.pop_back();
		}
	}
	//选择的话就是dfs(candidates,ans,candidates[i],)
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> combine;
		dfs(candidates, ans, combine, target, 0);
		return ans;
	}
};

4.实例3：LeetCode47全排列Ⅱ

5.实例4：LeetCode40组合总和II

6. 实例5：回溯法解0-1背包

上界函数：当前价值cw+剩余容量可容纳的最大价值 

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
double c;	//背包容量
int n;	//物品数量
double []w;	//物品数量数组
double []v;	//物品价值数组
double cw;	//当前重量
double cv;	//当前价值
double bestv;	//当前最优价值
double bound(int i){
    double cleft=c-cw;	//剩余容量
    double bestv = cv;	//当前价值
    //以物品单位重量价值递减序装入物品
    while(i<=n && w[i]<=cleft){
        cleft -= w[i];
        bestv += v[i];
        i++;
    }
    //装满背包
    if (i<=n)
        bestv+=v[i]+w[i]*cleft
    return bestv;	//返回计算出的上界
}
void backtrack(int i){
    if(i>n) {bestv=cv;return;}	//递归结束
    //如果左子节点可以，则直接搜索左子树
    //对于右子树，先计算上界函数，以判断是否将其减去
    if(cw+w[i]<c){
        cw+=w[i];
        cv+=v[i];
        backtrack(i+1);
        cw-=w[i];
        cv-=v[i];        
    }
    if(bound(i+1)>bestv){
        backtrack(i+1);
    }
}

7. 实例6：分支限界法求0-1背包问题