算法训练营第45天 | 动态规划（第七部分）：完全背包问题（LeetCode 70. 爬楼梯（进阶）、322. 零钱兑换、279. 完全平方数）

文章目录

• 70. 爬楼梯(进阶)(求排列方法数)
  • • 解题思路
    • 程序编写

  • 322. 零钱兑换(求等于背包重量的最小物品数)

  • • 解题思路
    • 程序编写
    • 思考与归纳

  • 279.完全平方数 (求等于背包重量的最小物品数)

  • • 解题思路
    • 程序编写

70. 爬楼梯(进阶)(求排列方法数)

题目链接🔥
假定当前处于爬楼梯的情境中。若需抵达楼顶，总共需要跨越 n 层台阶。
在每次移动过程中，可以选择攀登 1 或 2 级台阶。请问存在多少种不同的路径方式能够抵达楼顶？
注意：题目中所给定的 n 值为一个正整数。

示例 1： 输入数值为 2，输出结果为 2。解释如下：共有两种可行路径抵达楼顶。
分别是：先跨过 1 级台阶，再跨过 1 级台阶；或是直接跨过 2 级台阶。

示例 2： 输入数值为 3，输出结果为 3。解释如下：共有三种可行路径抵达楼顶。
具体包括：连续跨过三次 1 级台阶；先跨过 1 级台阶，再跨过 2 级台阶；或是先跨过 2 级台阶，再跨过 1 级台阶。

思路分析

在讲解这道题目时，由于尚未涉及背包问题的相关内容，因此仅介绍了爬楼