对网易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

相关推荐

秋盈丶:后续:我在宿舍群里和大学同学分享了这事儿,我好兄弟气不过把他挂到某脉上了,10w+阅读量几百条评论,直接干成精品贴子,爽
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务