{"id":10275,"date":"2025-04-05T21:11:01","date_gmt":"2025-04-06T04:11:01","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10275"},"modified":"2025-04-06T07:51:22","modified_gmt":"2025-04-06T14:51:22","slug":"leetcode-403-frog-jump","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-403-frog-jump\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 403. Frog Jump"},"content":{"rendered":"\n

\u80af\u5b9a\u662f\u7528DP\uff0c\u4f46\u6211\u81ea\u5df1\u60f3\u4e86\u4e00\u4e2a\u5947\u602a\u7684\u65b9\u6cd5\uff0c\u52c9\u5f3a\u8fc7\u4e86…<\/p>\n\n\n\n

\u4f7f\u7528dp[i] = {steps}\uff0c\u8868\u793a\u53ef\u4ee5\u8fbe\u5230stones[i]\u7684\u6700\u540e\u4e00\u8df3\u7684unit\u7684\u96c6\u5408\u3002
dp[0] = {0}
dp[1] = {1} if stones[1] = 1 else {}
\u7136\u540e\u5bf9\u4e8estones[i]\uff0c\u679a\u4e3e\u6240\u6709step – 1, step, step + 1\u4e09\u79cd\u60c5\u51b5\uff0c\u770b\u770b\u662f\u5426\u53ef\u4ee5\u8df3\u5230\u65b0\u7684\u77f3\u5934\u4e0a\u9762\uff08\u4f7f\u7528\u4e00\u4e2ahashtable\u5224\u65ad\uff09\uff0c\u5982\u679c\u53ef\u4ee5\u7684\u5427\uff0c\u628a\u8df3\u7684unit\u5b58\u5230dp[j]\u4e2d\u3002\u76f8\u5f53\u4e8e\u63a8\u4e86\u3002
\u9700\u8981\u4f7f\u7528hashset\u53bb\u91cd\uff0c\u4e0d\u7136\u4f1a\u8d85\u65f6\u3002<\/p>\n\n\n\n

\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n2<\/sup>)
\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(n2<\/sup>)<\/p>\n\n\n\n

\nclass Solution {\npublic:\n  bool canCross(vector& stones) {\n    if (stones[1] != 1) return false;\n    unordered_map m;\n    const int n = stones.size();\n    for (int i = 0; i < n; ++i)\n      m[stones[i]] = i;\n    \/\/ dp[i] = {steps} steps to jump to stone[i].\n    vector> dp(n);\n    dp[0] = {0};\n    dp[1] = {1};\n    for (int i = 2; i < n; ++i) {\n      for (int last : dp[i - 1]) {\n        for (int cur = last - 1; cur <= last + 1; cur++) {\n          if (cur < 1) continue;\n          const int t = stones[i - 1] + cur;\n          auto it = m.find(t);\n          if (it != end(m)) dp[it->second].insert(cur);\n        }\n      }\n    }\n    return !dp.back().empty();\n  }\n};\n<\/pre>\n\n\n\n
“\u4f18\u5316”\uff1a\u7531\u4e8e\u6bcf\u6b21\u53ea\u80fdk-1,k,k+1steps\uff0c\u6240\u4ee5\u6700\u5927\u7684units\u548cn\u662f\u7ebf\u6027\u5173\u7cfb\uff0c\u8fbe\u5230stones[i]\u6700\u591a\u8df3i+1\u4e2aunits\u3002
\u53ef\u4ee5\u7528\u4e8c\u7ef4\u6570\u7ec4dp[j][k] := \u662f\u5426\u53ef\u4ee5\u901a\u8fc7k\u6b65\u8df3\u5230stones[j].
dp[j][k] = dp[i][k-1] || dp[i][k] || dp[i][k+1], k = stones[j] – stones[i]. \u5373\u4ecestones[i]\u8df3\u5230stones[j]\uff0c\u5e76\u4e14\u8981\u6c42\u8df3\u5230stones[i]\u7684\u53ef\u80fd\u6b65\u6570\u4e2d\u5b58\u5728k-1,k,k+1\u3002
\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u7a7a\u95f4\u590d\u6742\u5ea6\u662f\u4e00\u6837\u7684\u3002<\/p>\n\n\n\n
\nclass Solution {\npublic:\n  bool canCross(vector& stones) {\n    const int n = stones.size();\n    vector> dp(n, vector(n + 1));\n    dp[0][0] = true;\n    for (int i = 1; i < n; ++i)\n      for (int j = 0; j < i; ++j) {\n        const int d = stones[i] - stones[j];\n        if (d >= n) continue; \/\/ undefined range.\n        dp[i][d] = dp[i][d] || (dp[j][d - 1] || dp[j][d] || dp[j][d + 1]);\n      }\n    return any_of(begin(dp.back()), end(dp.back()), [](bool x) { return x; });\n  }\n};\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u80af\u5b9a\u662f\u7528DP\uff0c\u4f46\u6211\u81ea\u5df1\u60f3\u4e86\u4e00\u4e2a\u5947\u602a\u7684\u65b9\u6cd5\uff0c\u52c9\u5f3a\u8fc7\u4e86… \u4f7f\u7528dp[i] = {steps}\uff0c\u8868\u793a\u53ef\u4ee5\u8fbe\u5230stones[i]\u7684\u6700\u540e\u4e00\u8df3\u7684unit\u7684\u96c6\u5408\u3002dp[0] = {0}dp[1] = {1} if stones[1] = 1 else {}\u7136\u540e\u5bf9\u4e8estones[i]\uff0c\u679a\u4e3e\u6240\u6709step – 1, step, step + 1\u4e09\u79cd\u60c5\u51b5\uff0c\u770b\u770b\u662f\u5426\u53ef\u4ee5\u8df3\u5230\u65b0\u7684\u77f3\u5934\u4e0a\u9762\uff08\u4f7f\u7528\u4e00\u4e2ahashtable\u5224\u65ad\uff09\uff0c\u5982\u679c\u53ef\u4ee5\u7684\u5427\uff0c\u628a\u8df3\u7684unit\u5b58\u5230dp[j]\u4e2d\u3002\u76f8\u5f53\u4e8e\u63a8\u4e86\u3002\u9700\u8981\u4f7f\u7528hashset\u53bb\u91cd\uff0c\u4e0d\u7136\u4f1a\u8d85\u65f6\u3002 \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n2)\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(n2) class Solution { public:…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,432],"class_list":["post-10275","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-jump","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10275"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10275\/revisions"}],"predecessor-version":[{"id":10280,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10275\/revisions\/10280"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}