关注
直觉告诉我贪心最快,但应该还有其它方法。我现在想用动态规划写出来,先抛砖引玉说下思路吧,用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 评论
相关推荐
打个响指吧c:把你电脑充电器拔了是啥意思哈哈哈
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 在大厂上班是一种什么样的体验 #
12798次浏览 173人参与
# 你的mentor是什么样的人? #
51263次浏览 724人参与
# 程序员找工作至少要刷多少题? #
21703次浏览 278人参与
# 我和mentor的爱恨情仇 #
106379次浏览 951人参与
# 论秋招对个人心气的改变 #
13920次浏览 193人参与
# 机械人避雷的岗位/公司 #
44312次浏览 311人参与
# 为了减少AI幻觉,你注入过哪些设定? #
6390次浏览 185人参与
# 秋招落幕,你是He or Be #
54349次浏览 618人参与
# 校招第一份工作你干了多久? #
136727次浏览 597人参与
# 高薪高压 vs 低薪wlb,你怎么选? #
47516次浏览 291人参与
# 设计人如何选offer #
189801次浏览 868人参与
# 考公VS就业,你怎么选? #
92032次浏览 507人参与
# 职场上哪些行为很加分? #
322732次浏览 3604人参与
# 你的秋招进行到哪一步了 #
2531769次浏览 23253人参与
# 牛客AI体验站 #
8089次浏览 213人参与
# 机械人还在等华为开奖吗? #
312276次浏览 1582人参与
# 秋招投递记录 #
381069次浏览 3204人参与
# 12306一秒售罄,你抢到回家的票了吗? #
2391次浏览 52人参与
# 我现在比当时_,你想录用我吗 #
9640次浏览 131人参与
# 重来一次,我还会选择这个专业吗 #
411457次浏览 3898人参与
美的集团公司福利 878人发布