力扣动态规划-1【算法学习day.95】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

---

习题

1.用最小花费爬楼梯

题目链接:746. 使用最小花费爬楼梯 - 力扣（LeetCode）

题面:

如果直接采取一般递归思路会超时，原因是递归了大量重复的层数，我们可以使用哈希表将每个第一次递归到的层数存一下，这样就不会超时了

哈希表代码:

class Solution {int[] cost;Map<Integer,Integer> map = new HashMap<>();public int minCostClimbingStairs(int[] cost) {this.cost = cost;return recursion(cost.length);}public int recursion(int u){if(u<=1)return 0;int flag = map.getOrDefault(u,-1);if(flag!=-1){return flag;}int res = Math.min(recursion(u-1)+cost[u-1],recursion(u-2)+cost[u-2]);map.put(u,res);return res;}
}

 代码:

class Solution {public int minCostClimbingStairs(int[] cost) {int f0 = 0, f1 = 0;for (int i = 1; i < cost.length; i++) {int newF = Math.min(f1 + cost[i], f0 + cost[i - 1]);f0 = f1;f1 = newF;}return f1;}
}

---

后言

上面是数据结构相关的习题，下一篇文章会将其他相关的习题。