前言：

这是之前做的一道笔试题，当时没写出来烦恼很久，这次记录一下。

题目链接：

Dotcpp--题目 1174: 计算直线的交点数

参考文章：

CSDN--槐阳7--计算直线的交点数

题目：

解题思考：

在当时做笔试时是知道用动态规划来做，也知道按平行线个数分类，但是依旧没有清晰的完成coding。现在复盘来看，错误点在于没有找一个基准（参考点），这才导致对平行的分类紊乱。

我们直接从4条直线入手，我们选取一条垂直轴作为所有直线的基准，将4条直线的相交情况分为4种小情况：

1条直线与垂直轴平行、2条直线与垂直轴平行

3条直线与垂直轴平行、4条直线与垂直轴平行

我们用m表示与垂直轴平行的直线个数，k表示不平行的直线个数。

图示如下：

易观察到：

当m = 1时，交点所有情况为k = 3条直线的所有交点情况 + 1 * 3；

当m = 2时，交点所有情况为k = 2条直线的所有交点情况 + 2 * 2；

当m = 3时，交点所有情况为k = 1条直线的所有交点情况 + 3 * 1；

当m = 4时，交点所有情况为k = 0条直线的所有交点情况 + 4 * 0；

综上：

对于 n 条直线来说，当有 m 条直线平行于垂直轴时，交点情况即为 k = n - m 条直线的交点情况加上 k * m。

我们即可根据以上信息来编写代码，由于本题 n 的范围只到20，所以我们一次将结果计算完后查表即可。

同时，由于 n 条直线最多有 $\frac{n(n - 1)}{2}$ 个交点个数，所以我们取一个 21 × 191的数组，

即 int[] lineCount[21][191];

其中 lineCount[n] 表示有n条直线，

lineCount[n][i] 表示 i 个交点数这种情况是否存在，1表示存在，0表示不存在。

示例代码：

#include<iostream>
using namespace std;void getAllAns();
//0 ~ 20 一共20种情况 n是正整数
//最多也就20 * 19
//20条直线最多191个交点
int lineCount[21][191] = { 0 };int main()
{getAllAns();int n;while (cin >> n) {for (int i = 0; i <= (n * (n - 1)) / 2; ++i) {if (lineCount[n][i] == 1) {cout << i << " ";}}cout << endl;}return 0;
}void getAllAns() {for (int i = 0; i < 21; i++) {lineCount[i][0] = 1;}//从2条直线开始，一直到20条直线for (int n = 2; n <= 20; n++) {//假设n = 4//m = 4, 3, 2, 1，即m条直线平行于垂直轴for (int m = n; m >= 1; m--) {//k为剩余不平行于垂直轴的直线数量int k = n - m;for (int i = 0; i <= (k * (k - 1)) / 2; i++) {//而k条直线最多也就(k * (k - 1)) / 2个交点//遍历这些交点个数，看是否存在if (lineCount[k][i] == 1) {//如果存在，则在该交点个数i的基础上在加mk个交点即可//对应的是n条直线，i + mk个交点是否存在lineCount[n][i + m * k] = 1;}}}}
}