对网易java方向第三题比较有兴趣,用C++写了一个dp

int main()
{
   int n,k;
  while(cin>>n>>k)
  {
     long sum=0;

     //创建二维数组
       int **dp=new int*[n];  for(int i=0;i<n;i++)  dp[i]=new int[k+1];

     //设置边值条件
       for(int i=0;i<n;i++)
        for(int j=1;j<=k;j++)
          if(i==n-1)
            dp[i][j]=1;
          else
            dp[i][j]=0;

     // dp算法
     for(int i=1;i<n;i++)
        for(int j=1;j<=k;j++)
         for(int m=1;m<=k;m++)
          if(j%m!=0||j<=m)
            dp[n-1-i][j]+=dp[n-i][m];

     //计算最总输出结果
      for(int i=1;i<=k;i++)
        sum+=dp[0][i];
      cout<<sum%1000000007;
  }
}
全部评论
思路是对的,但是会超时。符合时间复杂负要求的是先算前一层的总和,再减去这一层不符合条件的情况,这样才能过。
点赞 回复 分享
发布于 2017-08-13 13:38
这个肯定超时,要换个dp思路,找不符合的情况,然后减去这些不符合的情况
点赞 回复 分享
发布于 2017-08-13 12:55
网易笔试全是编程题吗
点赞 回复 分享
发布于 2017-08-13 11:09
https://www.nowcoder.com/discuss/32063?type=0&order=0&pos=14&page=1 这个帖子里就有这题,dp能通过。 只是有个问题,把dp数组放main外面就能通过,里面只能过90%,估计是全局变量的空间不在栈里所以不会有问题吧,不过为什么只有10%不能通过呢,开的dp数组大小一直是固定的呀?不明白
点赞 回复 分享
发布于 2017-08-13 10:03
确定能过?目测超时
点赞 回复 分享
发布于 2017-08-13 09:46
请问一下dp思路
点赞 回复 分享
发布于 2017-08-13 09:41

相关推荐

程序员牛肉:小牛肉来也! 基本破不了局了,我给你的建议是适当放弃秋招,投递大厂的日常实习之后赶明年的春招。 在没有实习的情况下,你的项目经历给面试官的作用就是提供提问点方便面试官来提问八股以及场景题而已。因此你现在简历的写法不太对,要着重突出项目中使用的技术点,而不是像你现在这个写的很宽泛。 最好是“基于xxxx技术解决了xxxx问题,解决了xxxx边缘场景问题”。最好是这样写,方便面试官对你的简历进行提问。 最后的最后,问题其实不在你。今年的秋招确实比较寒冬一点,所以找不到是正常的。要做好打持久战的准备。
Java学习交流
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-27 17:41
牛客34884196...:你期望薪资4-5k,那确实可以重生了,但很难在深圳活下去
点赞 评论 收藏
分享
09-18 14:40
门头沟学院 Java
多益网络为什么一面完还是等待面试啊,这是过了还是挂了啊
哆嗐网络受缢人:多在小红书 知乎之类的平台看看大家的评价,看看公司是如何对待应届生和老员工的吧。或者看看我的主页😭
我的秋招日记
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务