[LC 368]. Largest Divisible Subset

DP的思路。需要同时track两个东东:到目前为止subset的size,和到目前为止subset是什么。

想了两种做法。第一种:用List<Integer>[] dp 记录到目前为止的subset,通过比较dp[i] 和 dp[j]的size,就可以知道当前subset的size。

举例说明:[1,2,3,6],dp开始是[[1], [2], [3], [6]];2可以整除1,dp变为[[1], [2,1], [3], [6]];3可以整除1,dp变为[[1], [2,1], [3,1], [6]];6可以整除1,2,3,但2和3对应的dp[]的size要比1对应的dp的size要大,所以把2(或3)对应的dp加到6对应的dp中,dp变成[[1], [2,1], [3,1], [6,2,1]]。最后结果是dp[i] 中size最大的元素。

第一种做法比较慢。第二种思路差不多,但用两个int[] 分别track目前subset的size和前一个元素的位置。一个是int[] count,初始值都是1,另一个int[] pre,初始值都是-1。

举例说明:[1,2,3,6], count开始是[1,1,1,1], 2可以整除1,count变成[1,2,1,1],pre变成[-1,0,-1,-1];3可以整除1,count变成[1,2,2,1], pre变成[-1,0,0,-1];6可以整除1,2,3,但count对应2或3的值大于对应1的值,所以count变成[1,2,2,3], pre变成[-1,0,0,1]。最后结果需要scan count和pre,先找出count中最大值对应的位置,然后从这个位置开始,从pre中找到之前一个应该在subset中的元素,直到找到全部subset中的元素。count的最大值也可以不在最后通过scan array找到,在之前update count和pre的过程中记录一下即可。

正确解题重点是:开始之前需要sort数列。否则无法解决像[12, 3, 9]的情况:3和12是一个可以整除的pair,所以3对用的subset中有12,9和3也是可以整除的pair,所以9对应的subset中就包含了3对应的subset,也就包括了12,但9和12并不是可以整除的pair,所以结果是错的。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s