[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月前
【每日一题Day114】LC1223 掷骰子模拟 | 记忆化搜索+dp
【每日一题Day114】LC1223 掷骰子模拟 | 记忆化搜索+dp
54 0
|
算法
poj 1050 To the Max(最大子矩阵之和)
poj 1050 To the Max(最大子矩阵之和)
37 0
poj 1088 记忆化搜索||动态规划
记忆化搜索也也是采用递归深搜的对数据进行搜索,但不同于直接深搜的方式,记忆化搜索是在每次搜索时将得到的结果保存下来,避免了重复计算,这就是所谓的记忆化。记忆化应该是属于动态规划。
39 0
|
机器学习/深度学习
[LeeCode][动态规划][简单] 杨辉三角
[LeeCode][动态规划][简单] 杨辉三角
55 0
|
机器学习/深度学习 定位技术
【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp
思路:使用BFS搜索,队列中存放三元组[蛇尾的横轴坐标x,蛇尾的纵轴坐标y,蛇的状态],当蛇为水平时,状态为0;当蛇为竖直时,状态为1
130 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. 斐波那契数]
【Day13】LeetCode力扣刷题[面试题 17.19. 消失的两个数字][70.爬楼梯][746. 使用最小花费爬楼梯]
了解[面试题 17.19. 消失的两个数字][70.爬楼梯][746. 使用最小花费爬楼梯]。
114 0
【Day13】LeetCode力扣刷题[面试题 17.19. 消失的两个数字][70.爬楼梯][746. 使用最小花费爬楼梯]
HDU-2566,统计硬币(暴力 or DP)
HDU-2566,统计硬币(暴力 or DP)