力扣热题100------70.爬楼梯
动态规划法:
动态规划法介绍:
动态规划（Dynamic Programming，简称 DP）是一种用于解决多阶段决策问题的算法思想，它通过将复杂问题分解为更简单的子问题，并存储这些子问题的解以避免重复计算，从而高效地解决问题。动态规划通常用于优化问题，尤其是那些具有重叠子问题和最优子结构特性的问题。
核心概念
• 最优子结构：
• 一个问题的最优解可以由其子问题的最优解组合而成。换句话说，问题的解可以分解为若干个子问题的解。
• 例如，在爬楼梯问题中，到达第(n)阶的方法数可以由到达第(n-1)阶和第(n-2)阶的方法数组合而成。
• 重叠子问题：
• 在递归求解过程中，同一个子问题会被多次计算。动态规划通过存储这些子问题的解（通常使用一个数组或哈希表），避免重复计算，从而提高效率。
• 例如，在递归计算斐波那契数列时，会多次计算相同的值，而动态规划通过存储这些值来避免重复计算。
动态规划的优势
• 高效性：
• 动态规划通过存储子问题的解，避免了重复计算，大大提高了算法的效率。时间复杂度通常为(O(n))。
• 适用性：
• 动态规划适用于具有重叠子问题和最优子结构特性的问题，如背包问题、最长公共子序列、最短路径问题等。
• 可扩展性：
• 动态规划的思想可以扩展到多维问题，通过增加状态维度来解决更复杂的问题。
动态规划的局限性
• 空间复杂度：
• 动态规划通常需要额外的空间来存储子问题的解，空间复杂度可能较高。例如，爬楼梯问题的空间复杂度为(O(n))。
• 状态转移方程的推导：
• 动态规划的关键在于推导状态转移方程，这需要对问题有深入的理解和分析。
• 适用范围：
• 动态规划只适用于具有重叠子问题和最优子结构特性的问题，对于不符合这些特性的问题，动态规划可能不适用。
总结
动态规划是一种强大的算法思想，通过将复杂问题分解为更简单的子问题，并存储这些子问题的解，避免重复计算，从而高效地解决问题。爬楼梯问题是动态规划的经典应用之一，通过定义状态、初始化状态、状态转移和计算顺序，可以高效地求解问题。
案例
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示：
1 <= n <= 45
思路：采用动态规划法 在n为1的时候 只有一种方法能到达 在n为2的时候 有两种方式可以到达 在n大于3之后就有f(n)=f(n-1)+f(n-2)种方法到达 所以f(n)就是我们要求的答案
- 定义状态：• 使用数组 dp ，其中 dp[i] 表示到达第 i 阶的方法数。
- 初始化状态：• dp[1] = 1 • dp[2] = 2
- 状态转移：• 对于 i \geq 3 ，根据状态转移方程更新：
状态转移方程就为f(n)=f(n-1)+f(n-2) - 计算顺序：• 从第 3 阶开始，逐步计算到第 n 阶。
- 返回结果：• 最终结果为 dp[n] 。
class Solution {public int climbStairs(int n) {if(n<=2){return n;}int[] fire=new int[n+1];fire[1]=1;fire[2]=2;for(int i=3;i<n+1;i++){fire[i]=fire[i-1]+fire[i-2];}return fire[n];}
}