image.png

  1. class Solution:
  2.     def climbStairs(self, n: int) -> int:
  3.         # 状态 dp[i] 爬i阶的方法数
  4.         # if n <= 1:
  5.         #     return n
  6.         dp = [0 for i in range(n + 1)]
  7.         choices = (1, 2)
  8.         # dp[1] = dp[2] = 1
  9.         for i in range(1, n + 1):
  10.             for c in choices:
  11.                 if i - c < 0:
  12.                     continue
  13.                 dp[i] = max(dp[i] + dp[i - c], dp[i] + 1)
  14.                 # dp[i] = dp[i-1] + dp[i]
  15.         print(dp[n])
  16.         return dp[n]
  18. if __name__ == '__main__':
  19.     s = Solution()
  20.     s.climbStairs(0)

总结

  • 有点像完全背包问题。
    • 相同点
      • 都是计算方案总数
    • 不同点
      • 爬楼梯问题 相同选择周期出现，
      • 完全背包问题 选择是会被消费的。
  • 有点像找零钱问题
    • 相同点
      • 选择定义相同

      • 找零钱记录少零钱方案， 转移方程是dp[i] =max(dp[i-n]) + 1, n为面值
      • 爬楼梯记录所有方案,， 转移方程 dp[i] = sum(dp[i-n])
  • 可以用斐波那契数列求解