【Python】dp之组合问题

377. 组合总和 Ⅳ

https://leetcode.cn/problems/combination-sum-iv/

1.递归思路
- 确定出口，rest < 0 or rest == 0，分别返回0，1
- 确定递归体，每次递归进行循环（数字可以重复），p计数 p+=p(rest-i)

可以发现，时间复杂度是target ^ len(nums)，即kⁿ，指数，太高了

2.稍微剪枝一下
- 把rest < i的条件放在循环中，rest<0的话就不用进入下一层

时间复杂度依旧是指数级，底数为target，但是快了很多，可以从程序运行时间观测得出

3.dp思路
- 边界条件
- 构建dp[0 for _ in range(n+1)]，初始dp[0]=1
- 根据递归递推式，构建dp状态转移方程
important！！dp先写递推式，再构建状态转移方程，不然直接写dp谁会啊
效率优化很明显

from typing import List
import time
from functools import wraps

def time_cal(func):
    @wraps(func)
    def inner(*args, **kwargs):
        t1 = time.time()
        res = func(*args, **kwargs)
        t2 = time.time()
        print(f"程序耗费时间: {t2-t1} 秒")
        return res
    return inner

class Solution:
    @time_cal
    def a(self, nums: List[int], target: int) -> int:
        def process(nums, rest):
            if rest < 0:
                return 0
            if rest == 0:
                return 1
            p = 0
            for i in nums:
                p += process(nums, rest-i)
            return p 
        ans = process(nums, target)
        return ans

    @time_cal
    def b(self, nums: List[int], target: int) -> int:
        def process(nums, rest):
            if rest == 0:
                return 1
            p = 0
            for i in nums:
                if rest < i:
                    continue
                p += process(nums, rest-i)
            return p 
        ans = process(nums, target)
        return ans

    @time_cal
    def c(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1,target+1):  # 从1开始构建dp
            for num in nums:  # 如果 target > 当前值，dp[i] += dp[i-num]
                if i >= num:
                    dp[i] += dp[i-num]
        return dp[target]

s = Solution()
print(s.a(nums=[4,2,1], target=32))
print(s.b(nums=[4,2,1], target=32))
print(s.c(nums=[4,2,1], target=32))

494. 目标和

https://leetcode.cn/problems/target-sum/

递归思路：
- 确定递归出口，遍历完所有的数，且此时和为target，返回1，否则返回0，回溯
- 每个数可以加，也可以减，返回两种情况之和

相当easy，但是我憋不出dp方程了，麻了，我去看看大佬怎么写，未完待续

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        def dfs(rest, index):
            if index == len(nums):
                return 1 if rest == 0 else 0
            res = 0
            res += dfs(rest + nums[index], index + 1)  # 相加
            res += dfs(rest - nums[index], index + 1)  # 相减
            return res
        res = dfs(target, 0)
        return res