[递归][DP]n条直线最多分平面为几部分？

51nod 3035 划分平面
链接https://www.51nod.com/Challenge/Problem.html#problemId=3035
用n条直线，划分平面，最多能够划分为多少块？
例如：
1条可以划分为2块
2条可以划分为4块
3条可以划分为7块
输入
共一行：1个数n（1≤n≤10^9）
输出
输出共1行，对应划分的数量 Mod 10^9+7
数据范围
对于20%的数据，1≤n≤10；
对于44%的数据，1≤n≤20000；
对于100%的数据，1≤n≤10^9；
输入样例
3
输出样例
7

分析
递归

f(n)=2,when n=1 f(n)=f(n-1)+n,when n>1

递推

2+2+3+4+...+n=1+1+2+3+...+n=1+n*(n+1)/2

想用递归来写，这样会超时
记忆化递归呢？数组得开很大，空间花销太大

从记忆化递归到用动态规划dp来写，估计也不能全过，看看效果

代码如下

#include<iostream> #include<string> #include<cstring> #include<vector> using namespace std;const long long maxn=1e9+7;long long split(int n){long long dp[n+1];dp[1]=2;for(int i=2;i<=n;i++)dp[i]=i+dp[i-1];return dp[n]; } int main(){int n;cin>>n;long long result=split(n);cout<<result%maxn;}

好了，直接说公式1+n*(n+1)/2，这个直接AC
注意类型long long

#include<iostream> using namespace std;const long long maxn=1e9+7;int main(){long long n;cin>>n;long long result=1+n*(n+1)/2;cout<<result%maxn;}

总结

以上是生活随笔为你收集整理的[递归][DP]n条直线最多分平面为几部分？的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。