题目描述：

LeetCode 491. Increasing Subsequences

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

题目大意：

给定整数数组，输出其中所有的不重复非递减子数组。

注意：

1. 数组长度不会超过15。
2. 给定整数范围在[-100, 100]之间。
3. 给定数组可能包含重复，两个相同的整数应当认为是一个非递减子序列。

解题思路：

动态规划（Dynamic Programming）

状态转移方程： 详见代码

Python代码：

class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        dp = set()
        for n in nums:
            for y in list(dp):
                if n >= y[-1]:
                    dp.add(y + (n,))
            dp.add((n,))
        return list(e for e in dp if len(e) > 1)

 

本文链接：http://bookshadow.com/weblog/2017/01/22/leetcode-increasing-subsequences/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码