2.3 數(shù)組中?子序列列的個(gè)數(shù) ???? 1. 題?目描述 給定?個(gè)數(shù)組a （可能包含相同的數(shù)），求它有多少個(gè)不同的?序列。例如a={1,2,1,3}，?序列有{1}{2}{3}{1,2}{1,3}{1,2}{1,1}{1,3}{2,1}{2,3} {1,2,1}{1,2,3}{1,1,3}{2,1,3}等。 2. 分析與解法 ????♂??? 這個(gè)題本?不難，但是分析清楚不容易。我們?先假設(shè)?序列可以為空，最后減1就好了。假設(shè) dp[i]表?數(shù)列前i項(xiàng)構(gòu)成的不同?序列的個(gè)數(shù)。初值dp[0] = 1，因?yàn)橹挥?個(gè)空?序列。我們現(xiàn)在考慮 dp[i]：如果數(shù)列第i項(xiàng)在之前沒(méi)有出現(xiàn)過(guò)，是?個(gè)新數(shù)，顯然 dp[i] = dp[i - 1] * 2。這是因?yàn)榍?i-1)項(xiàng)的?序列本?，以及添加上第i項(xiàng)，都是?個(gè)?序列，這是?較容易的情況。如果全是這樣，??就完美了……因?yàn)槲覀儠?huì)推出 dp[i] = 2 ^ i，但還有討厭的第?種情況：如果第i項(xiàng)在之前出現(xiàn)過(guò)，假設(shè)j是它最近?次出現(xiàn)的位置，我們有 0 < j < i （注意i,j都是項(xiàng)數(shù)，或者說(shuō)下標(biāo)從1開(kāi)始的），那么我們直接乘以2，有些會(huì)重復(fù)。哪些重復(fù)了呢？原來(lái)的前(j-1)項(xiàng)的?序列末尾添加上第j項(xiàng)和添加上第i項(xiàng)是?樣的，就這些是重復(fù)的。所以 dp[j-1]是重復(fù)的。此時(shí) dp[i] = dp[i - 1] * 2 - dp[j - 1]。最后千萬(wàn)別忘記答案是 dp[n] - 1因?yàn)槲覀兛紤]了空的?序列。還有?種分析可以不考慮空的?序列，也是類似的。