记忆化搜索（1）：P1118 数字三角形——暴力dfs->找规律+最大最小值dfs剪枝_数字三角形最大和 记忆化搜索

P1118 数字三角形

输入输出样例
输入 #1复制
4 16
输出 #1复制
3 1 2 4
1
2
3
4
5

总结目录

1 本题搜索思路
2 本题减少复杂度的两个方法——找规律+过程剪枝

1 本题搜索思路

本题的搜索过程中，是使用类似于全排列的方法dfs。回溯打标记，dfs，去除标记就不再多说了。关键在于返回的条件。一开始按照模拟，我们全部搜索完之后，用一个bool ansIsOk(int n,int targetval) 来验证一个排列解是否合适。验证的过程无非是把数重新加一次，复杂度是n^2，比较和targetval的值。

使用暴力dfs可以得到70%的分数。也比较简单。

2 找规律与过程剪枝

找规律是指最后得到n个数的排列后，我们需要验证他们的和是否为targetval，实际上整个求和的过程是固定的（给定n）时，即系数是一定的。因此我们可以一开始就把系数计算好，利用查表得方式来求取和。这个方法可以将复杂度从n^2降低到n。

除此之外，由于n确定时系数是一定得，因此我们可以不全部求完n个数就进行剪枝，即由于我们是求和，对于n==4得情况，显然x,3,4,x这种排列是肯定不行的，因为33+44 == 9+16 == 25，其余两个数怎么加都是更大的。因此，我们在剪枝的时候，加入一个条件，即计算当前ans中的求和是否已经超过target，如果已经超过了，那么就直接返回就可以了。

代码 找规律+过程剪枝 AC

#include<iostream>
#include<algorithm>
#define maxsize 15
using namespace std;
int n, target;
int used[maxsize];
int ans[maxsize];
int res[maxsize];
int table[maxsize][maxsize];
bool flag = false;

//建立规律公式表，将计算复杂度从n^2降到n
void buildtable(int n) {
	table[1][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (j < i) {
				table[i][j] = table[i - 1][j] + table[i - 1][j - 1];
			}
			else if (i == j) {
				table[i][j] = 1;
			}
		}
	}
}


bool ansIsOk(int n,int targetval) {
	//计算ans中的n个数的当前组合是否满足targetval
	//ans[1,n]的计算，一共计算n次
	int tmp[maxsize];
	for (int i = 1; i <= n; i++) {
		tmp[i] = ans[i];;//拷贝数组
	}
	for (int i = n-1; i >=1 ; i--) {
		for (int j = 1; j <= i; j++) {
			tmp[j] = tmp[j] + tmp[j + 1];
		}
	}
	return tmp[1] == targetval;//判断是否等于具体值
}

//本题提升的关键是如何使得ansIsOk()这个函数得到简化
bool ansIsOk2(int currow, int targetval) {
	int res = 0;
	for (int i = 1; i <= currow; i++) {
		res += table[currow][i] * ans[i];
	}
	return res == targetval;
}

bool PreJudgeNotOk(int currow) {
	if (currow < n + 1) {
		int res = 0;
		for (int i = 1; i < currow; i++) {
			res += table[n][i] * ans[i];
		}
		if (res >= target) {
			return true;
		}
	}
	return false;
}


void dfs(int row) {
	//这里的框架仍然是先枚举，再判断。这里的枚举是先把数列排列出来，再另外去计算这个数列是否满足要求(作为返回要求）
	//row指准备填充row个数，已经填充row-1个数
	if (row < n + 1) {
		if (PreJudgeNotOk(row)) {
			return;
		}
	}

	if (row == n + 1) {
		if (ansIsOk2(n,target)) {
			flag = true;
			for (int i = 1; i <= n; i++) {
				res[i] = ans[i];
			}
			return;
		}
	}

	for (int i = 1; i <= n; i++) {//此处为枚举可能性
		if (flag == true) {
			break;//如果已经找到最小的排列，直接跳出
		}
		if (used[i] != 1) {
			used[i] = 1;
			ans[row] = i;//此处为将可能性带入当前的结点，即row结点
			dfs(row + 1);
			used[i] = 0;
		}
	}
}

int main() {
	cin >> n >> target;
	//从下往上搜索
	buildtable(n);
	dfs(1);//从第1个数排列到最后一个数
	if (flag == true) {
		for (int i = 1; i <= n; i++) {
			cout << res[i] << " ";
		}
	}
	else if (flag == false) {

	}
	return 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
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

暴力dfs（70%）

基于全排列方法的dfs，全排列的构造是通过dfs来实现的，然后就是使用了回溯算法。在到达尾部的时候，调用一个函数ansIsOk来判断结果是否符合。也就是把相邻的数字进行相加。符合就跳出，并且标记flag，不再进行后续的搜索。flag其实可以写到剪枝里面，也就是作为一开始return的一部分。

#include<iostream>
#include<algorithm>
#define maxsize 15
using namespace std;
int n, target;
int used[maxsize];
int ans[maxsize];
int res[maxsize];
bool flag = false;

bool ansIsOk(int n,int targetval) {
	//计算ans中的n个数的当前组合是否满足targetval
	//ans[1,n]的计算，一共计算n次
	int tmp[maxsize];
	for (int i = 1; i <= n; i++) {
		tmp[i] = ans[i];;//拷贝数组
	}
	for (int i = n-1; i >=1 ; i--) {
		for (int j = 1; j <= i; j++) {
			tmp[j] = tmp[j] + tmp[j + 1];
		}
	}
	return tmp[1] == targetval;//判断是否等于具体值
}

void dfs(int row) {
	//这里的框架仍然是先枚举，再判断。这里的枚举是先把数列排列出来，再另外去计算这个数列是否满足要求(作为返回要求）
	if (row == n + 1) {
		if (ansIsOk(n,target)) {
			flag = true;
			for (int i = 1; i <= n; i++) {
				res[i] = ans[i];
			}
			return;
		}
	}

	for (int i = 1; i <= n; i++) {//此处为枚举可能性
		if (flag == true) {
			break;//如果已经找到最小的排列，直接跳出
		}
		if (used[i] != 1) {
			used[i] = 1;
			ans[row] = i;//此处为将可能性带入当前的结点，即row结点
			dfs(row + 1);
			used[i] = 0;
		}
	}
}

int main() {
	cin >> n >> target;
	//从下往上搜索
	dfs(1);//从第1个数排列到最后一个数
	if (flag == true) {
		for (int i = 1; i <= n; i++) {
			cout << res[i] << " ";
		}
	}
	else if (flag == false) {

	}
	return 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64