Coding on 排列&背包问题

Example leetcode 排列&背包问题

Posted by Kylin on April 22, 2024

[TOC]

example. 377. 组合总和 Ⅳ

要我们求一个列表中等于target的取数序列(可重复、排列问题)

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0]*(target+1)
        dp[0] = 1
        for i in range(1,target+1):
            for num in nums:
                if i>=num:
                    dp[i]+=dp[i-num]
        return dp[target]

insight:两个for如果返过来,就是不考虑顺序的了(组合)