前言：

這是之前做的一道筆試題，當時沒寫出來煩惱很久，這次記錄一下。

題目鏈接：

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 條直線最多有??個交點個數，所以我們取一個 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;}}}}
}

測試結果：