关注
直觉告诉我贪心最快,但应该还有其它方法。我现在想用动态规划写出来,先抛砖引玉说下思路吧,用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 评论
相关推荐
牛客热帖
更多
正在热议
更多
# 技术岗笔试题求解 #
77594次浏览 1005人参与
# 拼多多求职进展汇总 #
642344次浏览 4983人参与
# 工作一周年分享 #
30698次浏览 179人参与
# 如果公司给你放一天假,你会怎么度过? #
16250次浏览 122人参与
# 作业帮求职进展汇总 #
55758次浏览 370人参与
# 华子oc时间线 #
1236419次浏览 6473人参与
# OPPO求职进展汇总 #
662180次浏览 5032人参与
# 总结:哪家公司面试体验感最差 #
60476次浏览 273人参与
# 职场上哪些事情令人讨厌 #
18719次浏览 91人参与
# 三一重工求职进展汇总 #
14313次浏览 65人参与
# 去年你投递实习了吗? #
21991次浏览 329人参与
# 这些公司卡简历很严格 #
41290次浏览 204人参与
# 扒一扒那些奇葩实习经历 #
66306次浏览 913人参与
# 经纬恒润求职进展汇总 #
121666次浏览 1032人参与
# 提前批过来人的忠告 #
113864次浏览 1194人参与
# 说说你知道的学历厂 #
58378次浏览 351人参与
# 秋招最大的收获是什么? #
36871次浏览 311人参与
# 找工作时的取与舍 #
80012次浏览 566人参与
# 你认为小厂实习有用吗? #
29311次浏览 341人参与
# 哪一瞬间觉得自己长大了 #
13908次浏览 327人参与