字节算法面试的一道DP题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了字节算法面试的一道DP题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含631字，纯文字阅读大概需要1分钟。

内容图文

题目：青蛙跳台阶吃虫子，数组arr代表每个台阶有多少个虫子，要求青蛙每次最多跳k个台阶，最多一共跳n次，计算青蛙最多能吃到多少个虫子？

例：arr=[8 10 9 7 17 13]  k=2 n=3 max=10+7+17=34

def mostinsects(arr,k,n):
    #arr 台阶数组
    #k 每次最多可以跳的台阶数
    #n 最多可以跳的次数
    #转移方程 DP[i][j] 代表在第i个台阶跳了j次后能吃到的最多虫子
    #DP[i][j]=max(DP[i-1][j-1],DP[i-2][j-1],...,DP[i-k][j-1])+arr[i]
    DP=[[0 for _ in range(n)] for _ in range(len(arr))]
    # DP[0][0]=0
    for i in range(k):
        DP[k][0]=arr[k]
    for i in range(len(arr)):
        for j in range(2,i):
            if j>=n:
                break
            else:
                mk=0
                for c in range(1,k+1):
                    mk=max(mk,DP[i-c][j-1])
                DP[i][j]=mk+arr[i]
    return max(DP[:][j-1])

内容总结

以上是互联网集市为您收集整理的字节算法面试的一道DP题全部内容，希望文章能够帮你解决字节算法面试的一道DP题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---