[LeeCode][动态规划][简单]上楼梯

简介: [LeeCode][动态规划][简单]上楼梯

class Solution {
    /** 
        递归处理: 由于上楼梯的方式只有两种, 即一次一个台阶 或者 一次两个台阶
        假如 一次一个台阶, 剩下 n - 1 台阶  也就是求 f(n - 1)
        假如 一次两个台阶,剩下 n - 2 台阶  也就是求 f(n - 2)
        那么综合两种可能, 求 n 阶台阶可能性f(n) 就是求 f(n - 1) + f(n - 2) 
     */
    Map<Integer, Integer> map = new HashMap<>();
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        // 缓存结果
        if (map.containsKey(n)) {
            return map.get(n);
        } else {
            int nSolution = climbStairs(n-1)+climbStairs(n -2);
            map.put(n, nSolution);
            return nSolution;
        }
    }
}
目录
相关文章
|
6月前
【每日一题Day242】LC1262可被三整除的最大和 | 贪心 dp
【每日一题Day242】LC1262可被三整除的最大和 | 贪心 dp
48 0
poj 1088 记忆化搜索||动态规划
记忆化搜索也也是采用递归深搜的对数据进行搜索,但不同于直接深搜的方式,记忆化搜索是在每次搜索时将得到的结果保存下来,避免了重复计算,这就是所谓的记忆化。记忆化应该是属于动态规划。
38 0
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP
|
机器学习/深度学习
[LeeCode][动态规划][简单] 杨辉三角
[LeeCode][动态规划][简单] 杨辉三角
54 0
|
机器学习/深度学习 定位技术
【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp
思路:使用BFS搜索,队列中存放三元组[蛇尾的横轴坐标x,蛇尾的纵轴坐标y,蛇的状态],当蛇为水平时,状态为0;当蛇为竖直时,状态为1
125 1
【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp
|
机器学习/深度学习 人工智能
51nod 1055 最长等差数列 (dp好题)
51nod 1055 最长等差数列 (dp好题)
50 0
【Day12】力扣LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]
了解LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]。
124 0
【Day12】力扣LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]
|
人工智能
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)