美丽的项链

美丽的项链

https://ac.nowcoder.com/acm/problem/14735

动态规划+背包问题
参考:https://blog.csdn.net/sinat_32403451/article/details/84899820
背包问题及变形:https://blog.csdn.net/qq_22526061/article/details/83504116

#coding:utf-8
n,m = map(int,input().split())
L=[]
R=[]
for i in range(n):
    li,ri = map(int,input().split())
    L.append(li)
    R.append(ri)

dp = [[0 for i in range(m+1)] for j in range(n)]

#初始化第一行
for i in range(L[0],R[0]+1):
    dp[0][i] = 1

#剩余其他行使用公式进行计算
for i in range(1,n):
    for j in range(m+1):
        left = max(0,j-R[i])
        right = max(0,j-L[i])
        for l in range(left,right+1):
            dp[i][j] += dp[i-1][l]
#print(dp)
print(dp[n-1][m])
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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