计算直线的交点数-动态规划解析（C++代码）

声明：这道题我开始也不会写，但看了别人的题解有了思路，过了一段时间自己再来写，发现自己可以理解了；

解题思路:

对这种题目我们往往无法直接看穿他的思路，像数学题中的找规律题型一样，重点是如何得到它的变化方程；

首先我们先定义以下几个变量

m：直线的总数

n：平行直线的数目

sum：交点个数；

这里我不做系统的规律分析，只讲一下我的思路：1.相互平行的直线有零个交点，不相互平行的直线之间一定有一个交点；我们假设有6条直线，其中2条平行，那么另外4条与这两条直线有2*4=8个交点，我们把这个部分定为part1，而4条互相不平行的直线有4*（4-1）/2=6个交点，我们把它称为part2，平行的两条直线之间交点数=0，我们定为part3（它总为零），显然从这里可以看出这是一个动态规划问题，那么重点就是状态转移方程：即sum = part1+part2（+part3 ）= n*（m-n） +  （m-n）条直线的交点数 （+ 0），我们把它称为（一）； 

注意事项:

但平行的直线数目n>=4时有不同的情况，需分别考虑；而这种特殊情况可以这样处理，即当m=4时，设平行线n=2，而另外两条线有两种情况：1，不平行，2，平行；而这不就是当n=2时所有可能交点的的情况吗？因而到这我们的状态转移方程应该改位：sum = part1 + part2（+part3） = n*（m-n） + (m-n)条直线交点的集合，我们把它称为（二），由以上分析，（二）是包含（一）的，所以我们最终的状态转移方程就是（二）

参考代码:

#include <iostream>
#include <cstdio>
#include <string.h>
#define limit_max 21
#define max_point 200

using namespace std;

int main()
{
    int M;      //直线的数目
    int r, c;   //行列下标
    int point[limit_max][max_point];
    memset(point, 0, sizeof(point));
    /**<
        行下标r代表直线数目，列下标c代表交点数目，
        而point[r][c]的值（0，1）则代表交点数是否存在
    */
    //first
    for(r=0; r<limit_max; r++)
        point[r][0] = 1;                    //对任意的r,当所有的直线互相平行时，c==0；
    for(r=2; r<limit_max; r++)
    {
        c = r*(r-1)/2;
        point[r][c] = 1;
    }
    //second
    int m, n;                               //直线数目m，平行直线数目n（n=1, 2, 3......m）;
    for(m=2; m<limit_max; m++)
        for(n=m-1; n>=2; n--)               //交点数sum = n*(m-n) + (m-n)条直线的交点数；
        {
           int  n_part = m-n;
           for(c=0; c<=n_part*(n_part-1)/2; c++)
           {
               if(point[n_part][c] == 1)
                    point[m][n*n_part+c] = 1;
           }
        }

    while (~scanf("%d", &M))
    {
        for(c=0; c<=M*(M-1)/2; c++)         // M*(M-1)/2 表示最大下标数
        {
            if(point[M][c])
                cout << c << ' ';
        }
        cout << endl;
    }

    return 0;
}