动态规划.pptx

文档介绍：2019/4/41今天,你了吗?AC2019/4/42每周一星(3):05059127陈谦益2019/4/43第四讲动态规划(1)(Dynamicprogramming)2019/4/44先热身一下——2019/4/45(1466)计算直线的交点数问题描述:平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。输入:n(n<=20)输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。样例输入4样例输出034562019/4/46初步分析:我们知道: n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,但本题不这么简单,因为问题问的是:这些直线有多少种不同的交点数?2019/4/47思考2分钟:如何解决?2019/4/48容易列举出N=1,2,3的情况:00,10,2,3如果已知<N的情况,我们来分析加入第N条直线的情况(这里N=4):1、第四条与其余直线全部平行=>无交点;2、第四条与其中两条平行,交点数为(n-1)*1+0=3;3、第四条与其中一条平行,这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交,因此可能交点数为:(n-2)*2+0=4或者(n-2)*2+1=54、第四条直线不与任何一条直线平行,交点数为:(n-3)*3+0=3或者(n-3)*3+2=5或者(n-3)*3+3=6即n=4时,有0个,3个,4个,5个,6个不同交点数。2019/4/49从上述n=4的分析过程中,我们发现:m条直线的交点方案数=(m-r)条平行线与r条直线交叉的交点数 +r条直线本身的交点方案=(m-r)*r+r条之间本身的交点方案数(1<=r<=m)2019/4/410一、数塔问题有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。