# coding = "utf-8"

'''
0-1背包：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485064&idx=1&sn=550705eb67f5e71487c8b218382919d6&chksm=9bd7f880aca071962a5a17d0f85d979d6f0c5a5ce32c84b8fee88e36d451f9ccb3bb47b88f78&scene=21#wechat_redirect
    dp[i][j]:前i个物品，背包容量为j，此时的最大价值
    状态：
        1. 装进背包（放得下）
        2. 不装进背包（放不下）
子集背包：

完全背包：物品数量是无上限的
'''


def canPartition(nums):
    '''
    给你⼀个只包含正整数的⾮空数组 nums。请你判断是否可以将这个数组分割成两个⼦集，使得两个⼦集的元素和相等。
    leetcode:416. 分割等和⼦集
    input:nums = [1,5,11,5]
    output:true
    思路：
        1. 转换问题：给一个可装载重量为sum/2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满
        2. dp[i][j] = x表示，对于前i个物品，当前背包的容量为j时，若x为true，则说明可以恰好将背包装满，若x为false，则说明不能恰好将背包装满
        3.
    '''
    n, s = len(nums), sum(nums)
    if s % 2 != 0:
        return False
    s = int(s / 2)
    dp = [[False for _ in range(s + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        # base case
        # 因为背包没有空间的时候，就相当于装满了;而当没有物品可选择的时候，肯定没办法装满背包
        dp[i][0] = True
    for i in range(1, n + 1):
        for j in range(1, s + 1):
            print(nums[i - 1], j - nums[i - 1])
            if j - nums[i - 1] < 0:
                # 装不下
                dp[i][j] = dp[i - 1][j]
            else:
                # 装得下 如果不装，则取决于上一个状态；如果装，则取决于背包剩余容量的状态
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
    print(dp[n][s])
    return dp[n][s]


def findTargetSumWays(nums, target):
    '''
    给你⼀个整数数组 nums 和⼀个整数 target，向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造⼀个表达式。
    例如，nums = [2, 1]，可以在 2 之前添加 '+'，在 1 之前添加 '-'，然后串联起来得到表达式 "+2-1"。
    返回可以通过上述⽅法构造的、运算结果等于 target 的不同表达式的数⽬。
    leetcode:494. ⽬标和
    input:nums = [1,1,1,1,1], target = 3
    output:5
    思路：
        1. 此题可以使用回溯法做
        2. 动态规划做法是转化问题，sum(A) = (target + sum(nums)) / 2 nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？
        3.
    '''
    n, s = len(nums), sum(nums)
    if s < target or (s + target) % 2 == 1:
        return 0
    s = int((s + target) / 2)
    dp = [[0 for _ in range(s + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        # base case 背包为0的时候，不放入也是一种选择
        dp[i][0] = 1
    for i in range(1, n + 1):
        for j in range(1, s + 1):
            if j - nums[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]

    print(dp[n][s])
    return dp[n][s]


def change(amount, coins):
    '''
    给你⼀个整数数组 coins 表示不同⾯额的硬币（硬币个数⽆限），另给⼀个整数 amount 表示总⾦额。
    请你计算并返回可以凑成总⾦额的硬币组合数，如果任何硬币组合都⽆法凑出总⾦额，返回 0。
    leetcode: 518. 零钱兑换 II
    input: amount = 5, coins = [1, 2, 5]
    output: 4
    思路：
        1.
        2.
        3.
    '''
    n = len(coins)
    dp = [[0 for _ in range(amount + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        for j in range(1, amount + 1):
            if j - coins[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                # 由于硬币是无限的，所以不选择该硬币时，dp[i][j - coins[i - 1]]
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
    print(dp[n][amount])
    return dp[n][amount]


if __name__ == "__main__":
    # canPartition([1, 5, 11, 5])
    # findTargetSumWays([1, 1, 1, 1, 1], 3)
    change(5, [1, 2, 5])