直觉告诉我贪心最快,但应该还有其它方法。我现在想用动态规划写出来,先抛砖引玉说下思路吧,用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])。 按照这样递推就可以遍历所有的情况,不过复杂度很高,但是可以试用于其它各种情况。

相关推荐

威猛的小饼干正在背八股:挂到根本不想整理
点赞 评论 收藏
分享
牛客网
牛客企业服务