LeetCode算法训练-动态规划
2023-03-31 10:36:05 时间
欢迎关注个人公众号:爱喝可可牛奶
LeetCode算法训练-动态规划
理论知识
动态规划当前状态是由前一个状态推导出来的,而贪心没有状态的转移
动态规划需要借助dp数组,可能是一维也可能是二维的
- 首先要明确dp数组是用来干什么的,下标对应什么
- 状态如何转移 ? 也就是理清递推公式
- dp数组如何初始化
- 如何遍历
- 举个栗子模拟推导一遍
LeetCode 509. 斐波那契数
分析
F(n) = F(n - 1) + F(n - 2),其中 n > 1
代码
class Solution {
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int index = 2; index <= n; index++){
dp[index] = dp[index - 1] + dp[index - 2];
}
return dp[n];
}
}
LeetCode 70. 爬楼梯
分析
错误 没有理清递推函数
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2]+2;
}
return dp[n];
}
}
dp[i]表示到当前楼梯有多少种跳法,从这里可以往后跳一步或者两步,这样就建立了前后阶梯的关系,但是不能跳2个一步
当前阶梯跳数能由前一个阶梯跳一步或前两个阶梯跳两步得到
代码
class Solution {
public int climbStairs(int n) {
if(n == 1){
return 1;
}
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
LeetCode 746. 使用最小花费爬楼梯
整数数组 cost ,cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
分析
根据测试用例能够得出台阶顶部在哪里,cost[i] :从下标i-1爬一步,从i-2爬两步到台阶顶部
dp[i]表示爬到第i个台阶的最小花费,
状态转移:dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
代码
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len+1];
// 初始化
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i <= len; i++){
dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[len];
}
}
总结
- 搞清楚dp数组含义以及对应下标反映了什么状态
- 弄清楚转移公式
- 初始化
- 确定遍历顺序(这个和转移公式紧密相关)
- 模拟一下
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十