题解 | #Shopee的办公室(二)#

Shopee的办公室(二)

http://www.nowcoder.com/practice/a71f3bd890734201986cd1e171807d30

本题以动态规划考虑求解 小虾同学只能从两个方向走,即他在每一个坐标的走法是他在该位置前两个方向上坐标走法的和(动态规划分解子问题)。 具体用公式表示为

#状态转移方程
dp[i][j]=dp[i][j-1]+dp[i-1][j]

不能通过boss的位置,所以经过boss位置时,dp数组定义为0 具体代码如下:

x, y,n =map(int,input().split())
ls =[[0 for i in range(y+1)] for j in range(x+1)]

for i in range(n):
    a,b = map(int,input().split())
    ls[a][b]=1
dp = [[0 for i in range(y+1)] for j in range(x+1)]
for i in range(x+1):
    for j in range(y+1):
        if ls[i][j]==1:
            dp[i][j]=0
            continue
        if i==0 or j==0:
            dp[i][j]=1
        else:
            dp[i][j]=dp[i][j-1]+dp[i-1][j]
    
print(dp[x][y])
全部评论

相关推荐

小叮当411:应该是1-3个月吧
点赞 评论 收藏
分享
07-07 11:33
江南大学 Java
已经在暑假实习了 ,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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