algo/di-er-zhan-a01c6/tan-xin-le-9bedf/ru-he-yun--48a7c/

[giscus[bot]]

algo/di-er-zhan-a01c6/tan-xin-le-9bedf/ru-he-yun--48a7c/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 45. Jump G...

https://labuladong.github.io/algo/di-er-zhan-a01c6/tan-xin-le-9bedf/ru-he-yun--48a7c/

[GeorgeSmith215]

自底向上动规js解法
function jump(nums: number[]): number {
const n = nums.length
const dp = new Array(n).fill(n)
// base case
dp[n-1] = 0
for (let i = n - 2; i >= 0; i--) {
for (let j = 1; j <= nums[i]; j++) {
if (i + j >= n) break
dp[i] = Math.min(dp[i], dp[i + j] + 1)
}
}
return dp[0]
};

[GeorgeSmith215]

这个贪心算法有点像双指针，farthest先走，i到end后交换farthest和end后继续循环

[1009058470]

// 定义dp 是跳到当前需要的最小步数
class Solution {
public:
    int jump(vector<int>& nums) {
        // dp 跳到当前需要的最小步数
        vector<int> dp(nums.size(), nums.size()+1);
        int ans = nums.size();
        dp[0] = 0;
        for(int i = 1; i < nums.size(); i++) {
            for(int j = 0; j < i; j++) {
                
                if(j + nums[j] >= i) {
                    // cout << i << " : " << j ;
                    dp[i] = min(dp[i],dp[j]+1);
                }
            }
            // cout << endl;
        }

        // for(int i = 0; i < dp.size(); i++) {
        //     cout << dp[i] << " ";
        // }

        return dp[nums.size()-1];
    }
};

[1009058470]

时间复杂度o(n^2) 过不了