代码随想录算法训练营 day37 day38| 卡码网52.完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ 卡码网70. 爬楼梯 （进阶） 322. 零钱兑换 279

n, v = map(int,input().split())
weight=[]
value = []
for i in range(n):
    wi, vi = map(int, input().split())
    weight.append(wi)
    value.append(vi)

# 构建dp数组
dp = [0]*(v+1)
for i in range(n):
    for j in range(weight[i], v+1):
        dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
print(dp[v])

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [0]*(amount+1)
        dp[0]=1
        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                dp[j] += dp[j-coins[i]]
        return dp[amount]
        

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 相当于动态规划的完全背包的排列问题，因为要考虑顺序，则先遍历背包再遍历物品
        dp = [0]*(target+1)
        dp[0]=1
        for j in range(1, target+1):
            for i in range(len(nums)):
                if j >= nums[i]:
                    dp[j] += dp[j-nums[i]]
        return dp[target]
        

def climbStairs(n,m):
    """
    还是完全背包的排列问题，先遍历背包再遍历物品，dp[j]是背包容量为j的时候的走法；
    递推公式里自加的原因是，比如一次能爬一阶或者爬两阶，
    那么到达当前位置的方法数等于到达前一阶的方法数加上到达前两阶的方法数，因为从前一阶到当前位置就一种走法
    """
    dp = [0]*(n+1)
    dp[0]=1
    for j in range(1, n+1):
        for i in range(1, m+1):
            if j>=i:
                dp[j] += dp[j-i]
    return dp[n]
    
if __name__ == "__main__":
    n, m = map(int, input().split())
    print(climbStairs(n, m))
        

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [float('inf')]*(amount+1)  # 设置初始值均为无穷大
        dp[0] = 0
        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                if dp[j-coins[i]] != float('inf'):  # 如果前一项不是无穷大，则进行状态转移
                    dp[j] = min(dp[j], dp[j-coins[i]]+1)
        if dp[amount] == float('inf'):
            return -1
        else:
            return dp[amount]
        

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [float('inf')]*(n+1)
        dp[0]=0
        for i in range(1, int(n**0.5)+1):
            for j in range(i*i, n+1):
                dp[j] = min(dp[j], dp[j-i*i]+1)
        return dp[n]

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # 这可以用完全背包的排列问题思考
        wordSet  = set(wordDict)
        n = len(s)
        dp = [False]*(n+1)
        dp[0] = True
        for j in range(1, n+1): # 遍历背包
            for i in range(j):   # 遍历单词
                if dp[i] and s[i:j] in wordSet:
                    dp[j] = True
                    break
        return dp[n]