每日一题 LeetCode 491. 递增子序列 【递推】【递增子序列】【动态规划】

题目链接

https://leetcode-cn.com/problems/increasing-subsequences/

题目说明

题解

主要方法：递推；动态规划

解释说明：

数据表示：观察数据范围（-100 ~ 100），设定一个201的 ans 数组，第 i 个元素存储以 i 为结尾的子结果

数据推导：

遍历给定的 nums 数组
对于每一个数 num，从 ans[0] 遍历到 ans[num+100]（ans表示在nums当前数之前已经存储的子结果，限定在 ans[0] 到 ans[num+100], 即找到以-100到当前num为结尾的子结果）
在上一步遍历出的所有 ans 中的子结果，末尾添加当前数num，并放在 ans[num+100] 结果里面（注意去重）
最后将该num以一个单元素列表存放至 ans[num+100]（注意去重）

数据输出： 将 ans 按输出要求进行flatten操作，以及除去单元素列表

代码示例：

class Solution:

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:

        ans = [[] for _ in range(201)]

        for idx, num in enumerate(nums):

            ans_ls = ans[num + 100][:]

            for res_ls in ans[:num+101]:

                for res in res_ls:

                    # print(res)

                    tmp_res = res[:]

                    tmp_res.append(num)

                    if tmp_res not in ans[num+100]:

                        ans_ls.append(tmp_res)

            if [num] not in ans_ls:

                ans_ls.append([num])

            ans[num + 100] = ans_ls

        ans = [res for res_ls in ans for res in res_ls if len(res)>1]

        return ans

每日一题 LeetCode 491. 递增子序列 【递推】【递增子序列】【动态规划】的相关教程结束。