【C++算法入门】动态规划/贪心算法-跳跃问题

本题取自力扣45题跳跃游戏。一 原题复现给定一个数组jump长度为njump[i]代表在i位置能跳的最远距离即能从1-jump[i]任选一个长度跳跃。求跳到最后一个位置n所需要的最少跳跃次数。二 思路分析和代码实现一动态规划1.1 思路分析首先我们不妨创建一个dp数组来记录跳跃到每个位置所需的最小跳跃次数。遍历jump数组再遍历jump[i]所能达到的距离并不断优化dp[i]找到最小值。对于这道题动态规划的核心就是穷尽所有情况利用动态转移方程和条件判断优化答案。我们举个例子加以说明jump{2,3,1,1,4}从第一个元素开始dp[0]0此时jump[0]2易得dp[1]1,dp[2]1;第二个元素dp[1]1此时jump[1]3易得dp[2]2,dp[3]2,dp[4]2。仔细观察可以发现这里求得的dp[2]2,大于前面所求的dp[2]1的结果。我们是否能写出状态转移方程呢dp[j]max(dp[j],dp[i]1)。各位可以继续推导来验证这个方程在此我就不做过多赘述了。下面是我的代码。1.2 代码实现二贪心算法2.1 思路分析对于本题来说利用贪心算法就是要找到一步能走到的最大距离但是每一步只走最大距离显然是不行的还要在这最大的距离之内判断下一步能走的最大距离。我们不妨利用上面提到的例子加以说明jump{2,3,1,1,1,4}。从第一个元素开始目前所在的位置curr_dis0最大跳跃距离jump[0]2此时能走到的最远位置max_dis2。当curr_dis1jump[1]3max_dis4......那么问题来了怎么判断什么时候走出这一步。既然第一步最大是2可以当curr_dis2时判断为已经走出第一步。在这期间我们更新了max_dis4并在curr_dis4时判断为已经走出第二步并更新max_dis5.....那么代码就可以完成了。2.2 代码实现三 总结就本题来说动态规划的思路较为简单但像边界条件dp数组初始化等细节方面的问题需要做好。贪心算法时间复杂度小但思考起来较为复杂且所需要注意的细节较多新手小白难以做到完美。算法练习可不能光停留在思考上仍需要动手写代码等代码真正能够落实了而后才算学懂了。