问题描述：
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
输入：n（n<=20）
输出：每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数。
样例输入
4
样例输出
0 3 4 5 6
【分析】
我们知道:
n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,
但本题不这么简单，因为问题问的是：这些直线有多少种不同的交点数？
容易列举出N=1,2,3的情况：
0
0，1
0，2，3
我们来分析N=4的情况：
【动态规划|计算直线的交点方案数】4条平行 第四条与其余直线全部平行 => 无交点；
3条平行 第四条与其中两条平行，交点数为(n-1)*1+0=3;
2条平行 第四条与其中一条平行，这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数为：（n-2）*2+0=4 或者 (n-2)*2+1=5
0条平行 第四条直线不与任何一条直线平行，交点数为：
(n-3)*3+0=3 或者 (n-3)*3+2=5 或者 (n-3)*3+3=6
即n=4时，有0个，3个，4个，5个，6个不同交点数。
假设一共有n=a+b条直线
（即n条直线分成2组，分别为a条和b条）
则总的交点数= a内的交点数
＋b内的交点数
＋a，b之间的交点数
我们将n条直线分为两部分,平行的直线数目r，和不平行的数目n-r；
分析可以知道r的取值是0<=r<=n;
n条直线相交的方案数
=(n-r）条平行线的交点方案（为0）+r条直线本身的交点方案+（n-r）条平行线与r条直线交叉的交点数方案
= r条直线本身的交点方案 +（n-r）条平行线与r条直线交叉的交点数方案。
=（m-r）*r+r条之间本身的交点方案数（0<=r<=n）
#include
using namespace std;
int dp[21][200];
//dp[i][j]=1表示存在i条直线交点方案数为j；
int main()
{
for(int i=1;
i<=20;
i++)
{
dp[i][0]=1;
}for(int i=2;
i<=20;
i++)
{
for(int j=0;
j<=i;
j++)
{
for(int k=0;
k<190;
k++)
{
if(dp[j][k]==1)
{
dp[i][(i-j)*j+k]=1;
}
}
}
}for(int i=1;
i<=6;
i++)
{
for(int j=0;
j<=190;
j++)
{
if(dp[i][j]==1)
{
cout< 推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- LeetCode-28 实现strStr() KMP算法
- leetcode|递归、动态规划--Leetcode(python)