爬楼梯问题

人们常见的爬楼梯问题就是青蛙跳台阶问题,变态青蛙跳台阶问题。

刚刚接触这类问题时,认为这种问题就是斐波拉契问题,使用递归解决。

青蛙跳台阶:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

fib = lambda n:n if n<=2 else fib(n-1)+fib(n-2)

变态青蛙跳台阶问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

fib = lambda n:n if n<=2 else 2*fib(n-1)



其实这类问题是动态规划问题,

定义状态dp[i],dp[i]代表跳上i级台阶时总的跳法。

对于青蛙跳台阶,状态转移方程为:dp[i] = dp[i-1]+dp[i-2]

def func(n):
    dp = [0 for _ in range(n)]
    dp[0],dp[1]=1,2
    for i in range(2,n):
        dp[i] = dp[i-1]+dp[i-2]
    return dp[n-1]

对于变态青蛙跳台阶,状态转移方程为:dp[i] = 2*dp[i-1]

def func(n):
    dp = [0 for _ in range(n)]
    dp[0],dp[1]=1,2
    for i in range(2,n):
        dp[i] = 2*dp[i-1]
    return dp[n-1]


对于这种问题的变体还有一次上2的阶乘个台阶问题,零钱找零问题。

一只青蛙一次可以跳上2k个台阶,求跳上n级台阶总共有多少种跳法?

def upstairs(n):
    dp = [0]*(n+1)
    dp[0] = 1
    for i in range(1,n+1):
        j = 1
        while j<=i:
            dp[i] += dp[i-j]
            j *= 2
    return dp[n]


零钱找零:给定一些不同面值的硬币coins,给定一张面值为amount的纸币,计算找开这这张纸币所需的最小硬币数目。

例如coins=[1,2,5],amount=11

类比上台阶,一次可以上1,2,5步,问走上11级台阶所需的最小步数。

注意这里不是多少种走法,而是最小步数,所以状态定义变了,dp[i]应该是上到第i级台阶所需的最小步数

def coinChange(coins, amount: int) -> int:
        if amount == 0 or not coins:
            return 0
        dp = [float('inf') for _ in range(amount+1)]
        dp[0] = 0

        for i in range(1,amount+1):
            for j in range(len(coins)):
                if i >= coins[j]:
                    dp[i] = min(dp[i],dp[i-coins[j]]+1)

        return dp[amount] if dp[amount] != float('inf') else -1 # 找不开返回-1


评论

Live Sex Cams Free