{"id":136,"date":"2024-10-14T23:33:53","date_gmt":"2024-10-14T15:33:53","guid":{"rendered":"https:\/\/womeifei.cn\/?p=136"},"modified":"2024-12-06T15:01:34","modified_gmt":"2024-12-06T07:01:34","slug":"%e8%b7%b3%e8%b7%83%e6%b8%b8%e6%88%8f","status":"publish","type":"post","link":"https:\/\/womeifei.cn\/index.php\/2024\/10\/14\/%e8%b7%b3%e8%b7%83%e6%b8%b8%e6%88%8f\/","title":{"rendered":"\u8df3\u8dc3\u6e38\u620f||"},"content":{"rendered":"\n
\"\"<\/div><\/figure>\n\n\n\n

\u8fd9\u4e2a\u9898\u6211\u4e00\u5f00\u59cb\u60f3\u5230\u7684\u5c31\u662f\u52a8\u6001\u89c4\u5212,\u4f46\u5176\u5b9e\u53d1\u73b0\u8fd9\u4e2a\u65b9\u6cd5\u4e0d\u662f\u4f18\u6cd5,\u56e0\u4e3a\u7528\u5230\u4e86\u4e24\u5c42\u5faa\u73af,\u65f6\u95f4\u590d\u6742\u5ea6\u5927.<\/p>\n\n\n\n

\u4f46\u662f\u786e\u5b9e\u8fd9\u9898\u786e\u5b9e\u6709\u52a8\u6001\u89c4\u5212\u7684\u601d\u60f3 \u4ee3\u7801\u8d34\u5728\u8fd9\u91cc<\/p>\n\n\n\n

class Solution {
public:
\u00a0 \u00a0 int jump(vector& nums) {
\u00a0 \u00a0 \u00a0 \u00a0 vector dp(nums.size(), INT_MAX);
\u00a0 \u00a0 \u00a0 \u00a0 dp[0] = 0;<\/p>\n\n\n\n

\/\/dp[i]\u8868\u793a\u4ece\u521d\u59cb\u4f4d\u7f6e\u5230\u7b2ci\u4e2a\u4f4d\u7f6e\u7684\u6700\u5c11\u8df3\u8dc3\u6b21\u6570<\/p>\n\n\n\n

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 1; j <= nums[i]; j++) {
                if (i + j < nums.size()) {
                    dp[i + j] = min(dp[i + j], dp[i] + 1);
                }
            }
        }
        return dp[nums.size() – 1];
    }
    };<\/p>\n\n\n\n

\u8fd9\u9898\u7684\u53e6\u4e00\u4e2a\u65b9\u6cd5\u66f4\u76f4\u89c2 \u53ef\u4ee5\u4f7f\u7528\u8d2a\u5fc3\u7b56\u7565:<\/p>\n\n\n\n

\n

\u6bcf\u6b21\u627e\u5230\u53ef\u5230\u8fbe\u7684\u6700\u8fdc\u4f4d\u7f6e\uff0c\u5c31\u53ef\u4ee5\u5728\u7ebf\u6027\u65f6\u95f4\u5185\u5f97\u5230\u6700\u5c11\u7684\u8df3\u8dc3\u6b21\u6570<\/strong><\/p>\n\n\n\n

\u4f8b\u5982\uff0c\u5bf9\u4e8e\u6570\u7ec4 [2,3,1,2,4,2,3]\uff0c\u521d\u59cb\u4f4d\u7f6e\u662f\u4e0b\u6807 0\uff0c\u4ece\u4e0b\u6807 0 \u51fa\u53d1\uff0c\u6700\u8fdc\u53ef\u5230\u8fbe\u4e0b\u6807 2\u3002\u4e0b\u6807 0 \u53ef\u5230\u8fbe\u7684\u4f4d\u7f6e\u4e2d\uff0c\u4e0b\u6807 1 \u7684\u503c\u662f 3\uff0c\u4ece\u4e0b\u6807 1 \u51fa\u53d1\u53ef\u4ee5\u8fbe\u5230\u66f4\u8fdc\u7684\u4f4d\u7f6e\uff0c\u56e0\u6b64\u7b2c\u4e00\u6b65\u5230\u8fbe\u4e0b\u6807 1\u3002<\/p>\n\n\n\n

\u4ece\u4e0b\u6807 1 \u51fa\u53d1\uff0c\u6700\u8fdc\u53ef\u5230\u8fbe\u4e0b\u6807 4\u3002\u4e0b\u6807 1 \u53ef\u5230\u8fbe\u7684\u4f4d\u7f6e\u4e2d\uff0c\u4e0b\u6807 4 \u7684\u503c\u662f 4 \uff0c\u4ece\u4e0b\u6807 4 \u51fa\u53d1\u53ef\u4ee5\u8fbe\u5230\u66f4\u8fdc\u7684\u4f4d\u7f6e\uff0c\u56e0\u6b64\u7b2c\u4e8c\u6b65\u5230\u8fbe\u4e0b\u6807 4\u3002<\/p>\n\n\n\n

<\/p>\n<\/div>\n\n\n\n

class Solution {
public:
int jump(std::vector& nums) {
int jumps = 0, currentEnd = 0, farthest = 0;<\/p>\n\n\n\n

    for (int i = 0; i < nums.size() - 1; i++) {\n        \/\/ \u66f4\u65b0\u80fd\u8fbe\u5230\u7684\u6700\u8fdc\u8ddd\u79bb\n        farthest = std::max(farthest, i + nums[i]);\n\n        \/\/ \u5982\u679c\u6211\u4eec\u5230\u4e86\u5f53\u524d\u8df3\u8dc3\u7684\u8fb9\u754c\uff0c\u5c31\u589e\u52a0\u8df3\u8dc3\u6b21\u6570\n        if (i == currentEnd) {\n            jumps++;\n            currentEnd = farthest;  \/\/ \u66f4\u65b0\u5f53\u524d\u8fb9\u754c\n        }\n    }\n\n    return jumps;\n}<\/code><\/pre>\n\n\n\n
};<\/p>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u4e2a\u9898\u6211\u4e00\u5f00\u59cb\u60f3\u5230\u7684\u5c31\u662f\u52a8\u6001\u89c4\u5212,\u4f46\u5176\u5b9e\u53d1\u73b0\u8fd9\u4e2a\u65b9\u6cd5\u4e0d\u662f\u4f18\u6cd5,\u56e0\u4e3a\u7528\u5230\u4e86\u4e24\u5c42\u5faa\u73af,\u65f6\u95f4\u590d\u6742\u5ea6\u5927. \u4f46\u662f\u786e\u5b9e\u8fd9\u9898 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18,4,7],"tags":[],"class_list":["post-136","post","type-post","status-publish","format-standard","hentry","category-18","category-4","category-7"],"_links":{"self":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/136","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/comments?post=136"}],"version-history":[{"count":1,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/136\/revisions"}],"predecessor-version":[{"id":138,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/136\/revisions\/138"}],"wp:attachment":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/media?parent=136"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/categories?post=136"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/tags?post=136"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}