LeetCode 45 Jump Game II 区间DP
2022/5/1 6:13:11
本文主要是介绍LeetCode 45 Jump Game II 区间DP,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Given an array of non-negative integers nums
, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.
Solution
很容易想到 \(dp[i]\) 表示以 \(i\) 结尾时的最小步数,考虑如何转移:
可以发现正向的 \(dp\) 比较容易:
点击查看代码
class Solution { public: int jump(vector<int>& nums) { int MAX = 9999999; int dp[10005]; int n = nums.size(); for(int i=0;i<n;i++)dp[i] = MAX; dp[0] = 0; if(n==1)return 0; else{ for(int i=0;i<n;i++){ for(int ach = i+1;ach <= i+nums[i] && ach<n;ach++){ dp[ach] = min(dp[ach],1+dp[i]); } } return dp[n-1]; } } };
这篇关于LeetCode 45 Jump Game II 区间DP的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升