cae0412 2022-05-24 17:33 采纳率: 100%
浏览 16
已结题

动态规划求一下这个时间复杂度

for(int i=1; i<=n*m; i++)
for(int j=0; j<=14; j++)
{
if(j==0)//只有一种情况,由dp[i-1][j+5]+b[i]的情况也就是上一段有5的气然后用掉了
dp[i][j]=dp[i-1][j+5]+b[i];
else if(j<10)//有两种情况,1,由上一段直接跑过来,2,由上一段消耗一张加速卡跑过来;
dp[i][j]=min(dp[i-1][j-1]+a[i],dp[i-1][j+5]+b[i]);
else if(j==10)//有两种情况,1,由上一段直接跑过来,2,由上一段的14+1变成10跑过来;
dp[i][j]=min(dp[i-1][j-1]+a[i],dp[i-1][14]+a[i]);
else if(j>10)//只有一种情况,由上一段路直接跑过来;
dp[i][j]=dp[i-1][j-1]+a[i];
}

  • 写回答

1条回答 默认 最新

  • 20240357 2022-05-24 20:48
    关注

    O(n^2)
    很明显,两层循环
    第一层平方级别
    第二层常数级别
    所以是平方级别

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 6月2日
  • 已采纳回答 5月25日
  • 创建了问题 5月24日

悬赏问题

  • ¥60 版本过低apk如何修改可以兼容新的安卓系统
  • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
  • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
  • ¥50 有数据,怎么用matlab求全要素生产率
  • ¥15 TI的insta-spin例程
  • ¥15 完成下列问题完成下列问题
  • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
  • ¥15 YoloV5 第三方库的版本对照问题
  • ¥15 请完成下列相关问题!
  • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?