关注
直觉告诉我贪心最快,但应该还有其它方法。我现在想用动态规划写出来,先抛砖引玉说下思路吧,用dp[a,b]表示a x b网格下最少的物件数量,其中a<b。初始化dp[1,1]=1,dp[1,3]=1,dp[3,3]=1,dp[1,2]=2,dp[2,3]=2.....(就是把3x3方格的全部初始化就行)
处理好边界dp[1,n]=min((dp[1,n-1]+dp[1,1]),(dp[1,n-3]+dp[1,3]))。
处理好边界dp[2,n]=min((dp[2,n-1]+dp[1,2]),(dp[2,n-3]+dp[2,3]))。
于此同理处理dp[3,n]。
然后dp[m,n]=min((dp[m-1,n]+dp[1,n]),(dp[m-2,n]+dp[2,n],dp[m-3,n]+dp[3,n])。
按照这样递推就可以遍历所有的情况,不过复杂度很高,但是可以试用于其它各种情况。
查看原帖
2 评论
相关推荐
mmvvcc:没通过你就偷着乐吧,这样的进去你天天受气
点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
444750次浏览 4542人参与
# 春招别灰心,我们一人来一句鼓励 #
42577次浏览 542人参与
# 地方国企笔面经互助 #
8025次浏览 18人参与
# 同bg的你秋招战况如何? #
77904次浏览 572人参与
# 实习必须要去大厂吗? #
55889次浏览 962人参与
# 虾皮求职进展汇总 #
117396次浏览 892人参与
# 如果你有一天可以担任公司的CEO,你会做哪三件事? #
11860次浏览 301人参与
# 实习,投递多份简历没人回复怎么办 #
2455521次浏览 34866人参与
# 提前批简历挂麻了怎么办 #
150035次浏览 1980人参与
# 在找工作求抱抱 #
906327次浏览 9423人参与
# 如果公司给你放一天假,你会怎么度过? #
4786次浏览 57人参与
# 你投递的公司有几家约面了? #
33224次浏览 188人参与
# 投递实习岗位前的准备 #
1196256次浏览 18551人参与
# 机械人春招想让哪家公司来捞你? #
157688次浏览 2267人参与
# 双非本科求职如何逆袭 #
662614次浏览 7397人参与
# 发工资后,你做的第一件事是什么 #
12862次浏览 62人参与
# 工作中,努力重要还是选择重要? #
36142次浏览 384人参与
# 简历中的项目经历要怎么写? #
87015次浏览 1517人参与
# 参加完秋招的机械人,还参加春招吗? #
20185次浏览 240人参与
# 我的上岸简历长这样 #
452150次浏览 8091人参与