Generate play list

Get a songs list and a target number. Generate a play list have target number of songs. The songs can repeat but should not as same as the last song.

Ex: songs = [0,1,2,3,4,5,6,7] target = 10 playlist: [0,1,0,1,2,3,4,5,6,7] is a valid list [0,0,1,2,3,4,5,6,7,0] is not return number of result play list.

中文描述：假如我有8首不同的歌 我想做一个10首歌的歌单。这个歌单要包含所有的歌，所以我肯定要重复二首歌。现在又有一个条件，就是这个歌单里，如果要重复一首歌，那必须在这之前放了1首不同的歌。那么共能生成多少个这种歌单.

思路：dfs可以暴力枚举每一种可能。 简单来说，就是先取2首歌（因为顺序可能不一样，所以有8*7种可能）。然后开始用从第三首开始排列组合。每新加的歌曲可以来自于前面的老歌，也可以是新歌。代码如下。复杂度太高，所以只取了前两首直接做permutation。 写到这里我突然感觉可以用dp来做。欢迎大神指导。

class Solution(object):
    def playList(self, songs, target):

        self.res = 0

        for i in range(len(songs)):
            for j in range(len(songs)):
                if j!=i:
                    playlist = [songs[i], songs[j]]
                    remain_song = songs[:]
                    remain_song.remove(songs[i])
                    remain_song.remove(songs[j])
                    #self.dfs(playlist, remain_song, target - len(songs), target)

        playlist = songs[:2]
        remain_song = songs[2:]
        self.dfs(playlist, remain_song, target - len(songs), target)

        return self.res


    def dfs(self, playlist, songs, remain, target):

        # escape condition
        if remain<0:
            return

        if not songs:
            if remain==0:
                self.res += 1
            return

        # dfs 
        # pick a old song
        if remain>0:
            for repeat in playlist[:-1]:
                self.dfs(playlist + [repeat], songs, remain-1, target)

        # pick a new song
        for i in range(len(songs)):
            newsong = songs[i]
            self.dfs(playlist + [newsong], songs[:i] + songs[i+1:], remain, target)


songs = [0,1,2,3,4,5,6,7]
target = 10

so = Solution()
a = so.playList(songs, target)
print(a)