{"id":124938,"date":"2020-06-14T21:08:07","date_gmt":"2020-06-14T13:08:07","guid":{"rendered":"http:\/\/4563.org\/?p=124938"},"modified":"2020-06-14T21:08:07","modified_gmt":"2020-06-14T13:08:07","slug":"%e6%88%91%e6%83%b3%e9%97%ae%e4%b8%80%e9%81%93-leetcode-%e5%8f%98%e5%bd%a2%e9%a2%98%ef%bc%9a%ef%bc%8870%ef%bc%89%e7%88%ac%e6%a5%bc%e6%a2%af%ef%bc%88%e5%8f%98%e5%bd%a2%ef%bc%89","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=124938","title":{"rendered":"\u6211\u60f3\u95ee\u4e00\u9053 LeetCode \u53d8\u5f62\u9898\uff1a\uff0870\uff09\u722c\u697c\u68af\uff08\u53d8\u5f62\uff09"},"content":{"rendered":"
\n
\n
\n

\u6211\u60f3\u95ee\u4e00\u9053 LeetCode \u53d8\u5f62\u9898\uff1a\uff0870\uff09\u722c\u68af\uff08\u53d8\u5f62\uff09 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/i> 7<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u539f\u9898\uff1a \u5047\u8bbe\u4f60\u6b63\u5728\u722c\u68af\u3002\u9700\u8981 n \u9636\u4f60\u624d\u80fd\u5230\u8fbe\u9876\u3002<\/p>\n

\u6bcf\u6b21\u4f60\u53ef\u4ee5\u722c 1 \u6216 2 \u4e2a\u53f0\u9636\u3002\u4f60\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u65b9\u6cd5\u53ef\u4ee5\u722c\u5230\u9876\u5462\uff1f<\/p>\n

\u6ce8\u610f\uff1a\u7ed9\u5b9a n \u662f\u4e00\u4e2a\u6b63\u6574\u6570\u3002<\/p>\n

\u53d8\u5f62\uff1a \u5047\u8bbe\u4f60\u6b63\u5728\u722c\u68af\u3002\u9700\u8981 n \u9636\u4f60\u624d\u80fd\u5230\u8fbe\u9876\u3002<\/p>\n

\u6bcf\u6b21\u4f60\u53ef\u4ee5\u722c 1 \u6216 2 \u6216 3 \u4e2a\u53f0\u9636\uff0c\u4e14\u6bcf\u6b21\u4e0a\u7684\u53f0\u9636\u4e0d\u76f8\u540c\u3002\u4f60\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u65b9\u6cd5\u53ef\u4ee5\u722c\u5230\u9876\u5462\uff1f<\/p>\n

\u6ce8\u610f\uff1a\u7ed9\u5b9a n \u662f\u4e00\u4e2a\u6b63\u6574\u6570\u3002<\/p>\n

\u54e5\u54e5\u4eec \u8fd9\u4e2a\u53d8\u5f62 \u600e\u4e48\u89e3\u7b54 \uff1f \u600e\u4e48\u4e2a\u601d\u8def \uff1f<\/p>\n<\/p><\/div>\n

\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (49<\/span>) <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n
    \n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u6709\u6ca1\u6709\u5927\u4f6c\u53ef\u4ee5\u8bd5\u7740\u89e3\u51b3\u4e00\u4e0b \uff0c\u5f1f\u5f1f\u60f3\u4e86\u4e00\u5bbf\u6ca1\u601d\u8def <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : hello2060 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u5f88\u96be\u5417\uff1f\u5f00\u4e00\u4e2a\u6570\u7ec4 int ways[n + 1], \u7b54\u6848\u662f ways[n] \u521d\u59cb\u5316 ways[0] = 1, ways[1] = 1, ways[2] = 2, ways[3] = xx, ways[n] = ways[n – 1] + ways[n – 2] + ways[n – 3] ? \u4ec0\u4e48\u53eb\u6bcf\u6b21\u4e0a\u7684\u53f0\u9636\u4e0d\u540c <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : Vegetable <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u4ec0\u4e48\u53eb\u6bcf\u6b21\u4e0a\u7684\u53f0\u9636\u4e0d\u540c\uff1f\u8fd8\u80fd\u6709\u76f8\u540c\u7684\uff1f <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : winterfell30 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u6590\u6ce2\u90a3\u5951\u6570\u5217 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : Vegetable <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u6709\u70b9\u8bfb\u61c2\u4e86\uff0c\u8bd5\u8bf4\u6bcf\u6b21\u4e0a\u7684\u53f0\u9636\u6570\u4e0d\u80fd\u4e0e\u4e0a\u4e00\u6b65\u76f8\u540c\uff1f\u8fd9\u4e2a\u4e5f\u7b97\u53d8\u79cd\u5417\uff1f\u53ef\u4ee5\u8bf4\u8fd9\u662f\u53d8\u4e86\u4e2a\u6570\u5427 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : VoidChen <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u6211\u60f3\u95ee\u4e0b\u6709\u6ca1\u6709\u597d\u7684\u5237 leecode \u7684\u603b\u7ed3\u3002\u3002\u4e4b\u524d\u5728 github \u770b\u5230\u4e00\u4e2a\u6309\u7b97\u6cd5\u7c7b\u578b\u6765\u5206\u7c7b\u7684\uff0c\u6211\u4e0d\u77e5\u9053\u4fdd\u5b58\u5230\u54ea\u6ca1\u4e86\u3002\u3002 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : cheese <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @hello2060 #2
    @Vegetable #3
    \u5e94\u8be5\u7684\u610f\u601d\u662f\uff0c\u722c\u8fc7 1 \u4e4b\u540e\uff0c\u4e0b\u4e00\u6b21\u53ea\u80fd 2\uff0c3 \u3002\u6bcf\u6b21\u7684\u9009\u62e9\u53f0\u9636\u6570\uff0c\u4e0d\u80fd\u548c\u4e0a\u4e00\u6b21\u7684\u6570\u5b57\u76f8\u540c <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : leavan <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u54e6\u6211\u61c2\u4e86\uff0c\u5c31\u662f\u5176\u4ed6\u65b9\u6cd5\u8d70\u8fc7\u4e00\u6b21\u7684\u68af\u4e0d\u80fd\u518d\u8d70\u4e86\u5457\u3002\u90a3\u4e0d\u662f\u5f88\u7b80\u5355\u5417\uff1f\u4ece\u9876\u5f80\u56de\u770b\uff0c\u6700\u591a\u53ea\u6709\u4e09\u4e2a\u53f0\u9636\u53ef\u4ee5\u4e00\u6b65\u5230\u9876\uff0c\u90a3\u4e48\u6211\u4eec\u53ea\u9700\u8981\u8bc1\u660e\u8fd9\u4e09\u79cd\u65b9\u6cd5\u90fd\u53ef\u884c\u5c31\u884c\u4e86\uff0c\u6bcf\u6b21\u90fd\u5f80\u524d\u5404\u63a8\u4e09\u6b65\uff08\u5982\u679c\u6709\u4e00\u4e2a\u4e0d\u662f\u4e09\u6b65\u7684\uff0c\u90a3\u4e48\u52bf\u5fc5\u4f1a\u9020\u6210\u91cd\u590d\uff09\uff0c\u53d1\u73b0\u63a8\u5230\u8fb9\u754c\u5904\u4ecd\u7136\u4e0d\u4f1a\u91cd\u590d\uff0c\u6240\u4ee5\u6709\u4e09\u79cd\u65b9\u6cd5\u3002\u7b54\u6848\u5c31\u662f 3\uff0c\u5f53\u7136\u5982\u679c\u4f60 n \u53ea\u6709 1 \u6216 2 \u7684\u8bdd\u90a3\u4e48\u65b9\u6cd5\u4e5f\u76f8\u5e94\u51cf\u5c11\u3002 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : coderraven <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u600e\u4e48\u6709\u70b9\u4e8c\u53c9\u6811\u7684\u611f\u89c9
    \u7528\u8fc7 1\uff0c\u90a3\u4e48\u5de6\u53f3\u5b50\u6811\u5c31\u53ea\u80fd\u662f 2 \u548c 3 \u3002
    \u7528\u8fc7 2\uff0c\u90a3\u4e48\u5de6\u53f3\u5b50\u6811\u5c31\u53ea\u80fd\u662f 1 \u548c 3.
    \u7528\u8fc7 3\u2026.<\/p>\n

    \u6700\u540e\u518d\u8d70\u4e00\u6ce2\u6570\u503c\u548c\u662f n \u7684\u904d\u5386\uff1f <\/p><\/div>\n<\/p><\/div>\n<\/li>\n

  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : leavan <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @leavan \u65e0\u89c6\u6211\u8fd9\u6761\uff0c\u770b\u4e86\u5927\u5bb6\u7684\u56de\u590d\u53d1\u73b0\u6211\u7406\u89e3\u9898\u610f\u4e86\u3002 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : zhjy23212 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    dp \u91cc\u9762\u6bcf\u4e2a\u72b6\u6001\u5b58\u4e4b\u524d\u5230\u8fd9\u4e2a\u70b9\u7684\u6b65\u6570\uff0c\u4e0b\u6b21\u904d\u5386\u8df3\u8fc7\u8fd9\u51e0\u4e2a\u3002<\/p>\n

    \u57fa\u672c\u4e0a\u662f frog jump \u7684\u53d8\u4f53 <\/p><\/div>\n<\/p><\/div>\n<\/li>\n

  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @Vegetable \u6bd4\u5982 \u4e0a 2 \u9636 \u53ea\u53ef\u4ee5\u4e00\u6b21\u6027\u4e0a 2 \u7ea7 \u4e0d\u80fd\u662f 1 \u7ea7 1 \u7ea7 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : EggtartZ <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    `dp[n, 1] = dp[n – 3, 2] + dp[n – 4, 3]` \u8fd9\u6837\u7684\u610f\u601d\uff1f <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : leavan <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u5982\u679c\u662f\u8ddf\u4e0a\u4e00\u6b65\u7684\u53f0\u9636\u4e0d\u540c\u7684\u8bdd\uff0c\u90a3\u5c31\u52a8\u6001\u89c4\u5212\u3002
    “`
    ways[i][0] = ways[i – 1][1] + ways[i – 1][2]
    ways[i][1] = ways[i – 2][0] + ways[i – 2][2]
    ways[i][2] = ways[i – 3][0] + ways[i – 3][1]
    “` <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : hello2060 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u90a3\u5c31\u4e0d\u8981 int[n + 1] \u641e\u4e00\u4e2a\u6570\u636e\u7ed3\u6784\uff0c\u6bcf\u4e00\u4e2a\u4f4d\u7f6e\u5b58\u7740 1.\u5230\u8fd9\u91cc\u7684\u603b\u65b9\u6cd5\u6570 2. \u524d\u4e00\u6b65\u662f n-1 \u7684\u65b9\u6cd5\u4e66 3.\u524d\u4e00\u6b65\u662f n-2 \u7684\u65b9\u6cd5\u6570 4.\u524d\u4e00\u6b65\u662f n – 3 \u7684\u65b9\u6cd5\u6570<\/p>\n

    \u90a3\u4f60\u5230 n \u7684\u65b9\u6cd5\u6570 \u5c31\u662f \u8d70 2\uff0c3 \u5230 n-1 \u7684\u65b9\u6cd5\u6570 + \u8d70 1\uff0c3 \u5230 n -2 \u7684\u65b9\u6cd5\u6570 + \u8d70 1\uff0c2 \u5230 n-3 \u7684\u65b9\u6cd5\u6570 <\/p><\/div>\n<\/p><\/div>\n<\/li>\n

  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @hello2060 \u5927\u4f6c \u4f60\u8fd9\u4e2a\u7b2c\u4e09\u4e2a\u4e0d\u5bf9\u554a\u30021+1+2 = 4 \u7b2c\u4e09\u7ea7 \u90a3\u6709 4 \u79cd\u554a 3 \uff0c12 \uff0c21 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : hello2060 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @hejw19970413 \u7b2c\u4e09\u4e2a\u6211\u4e0d\u662f\u6ca1\u7b97\u561b xx \u53cd\u6b63\u5c31\u90a3\u4e2a\u610f\u601d\uff0c\u54c8\u54c8 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : Vegetable <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u5927\u6982\u60f3\u4e86\u4e00\u4e0b
    \u53ef\u4ee5\u91cd\u590d\u7684\u65f6\u5019\uff0cdp(n) = dp(n-1)+dp(n-2)+dp(n-3)
    \u4e0d\u80fd\u91cd\u590d\u7684\u8bdd\uff0c\u8ba1\u7b97\u70b9 n \u65f6\uff0c\u4ece n-2 \u5230 n-1 \u8fd9\u4e00\u70b9\u7684\u6570\u636e\u90fd\u662f\u8981\u53bb\u6389\u7684\uff0cn-4 \u5230 n-2 \u8981\u53bb\u6389\uff0cn-6 \u5230 n-3 \u8981\u53bb\u6389\u3002
    \u6240\u4ee5 dp(n) = (dp(n-1) – dp(n-2)) + (dp(n-2)-dp(n-4))+(dp(n-3)-dp(n-6))
    \u662f\u8fd9\u6837\u5417 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @Vegetable \u6211\u53bb\u8dd1\u4e00\u4e0b <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : xw900812 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    dynamic programming… YouTube \u641c huahua leetcode \u8bb2\u8fd9\u9053\u722c\u68af\u7684\u95ee\u9898\uff0c\u5f88\u7ecf\u5178\u7684 DP \u9898\u76ee <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : buhi <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u7b2c\u4e00\u4e2a\u9898\u5c31\u662f\u6590\u6ce2\u90a3\u5951\u6570\u5217, \u7b54 dp \u7684\u90fd\u8f93\u4e86
    const stair_ways = n => {
    return Math.round((1 \/ sqrt_5) * Math.pow((1 + sqrt_5) \/ 2, n + 1) – (1 \/ sqrt_5) * Math.pow((1 – sqrt_5) \/ 2, n + 1))
    } <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : MoYi123 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u4e09\u4e2a\u6570\u5b57\u7684\u6590\u6ce2\u90a3\u5951\u6570\u5217 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : EggtartZ <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    “`
    def solve(n, m):
    dp = [[0] * m for i in range(n)]
    for i in range(m):
    dp[i][i] = 1
    for j in range(i):
    dp[i][j] = sum(dp[i – j – 1]) – dp[i – j – 1][j]<\/p>\n

    for i in range(m, n):
    for j in range(m):
    dp[i][j] = sum(dp[i – j – 1]) – dp[i – j – 1][j]<\/p>\n

    return sum(dp[n – 1])
    “`
    \u5927\u6982\u662f\u8fd9\u6837\u5427 <\/div>\n<\/p><\/div>\n<\/li>\n

  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : mymike <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u8fd9\u4e2a\u548c\u6700\u8fd1\u7684\u5237\u623f\u5b50\u7c7b\u4f3c \u9700\u8981\u52a0\u4e00\u4e2a\u7ef4\u5ea6 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : larisboy <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u6570\u7ec4+\u6590\u6ce2\u90a3\u5951\u6570\u5217 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : hello2060 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @buhi \u6590\u6ce2\u90a3\u5951\u5c31\u662f DP \u554a\uff0c\u4e00\u4e2a\u95ee\u9898\u53ef\u4ee5\u5206\u89e3\u6210\u7c7b\u4f3c\u7684\u5b50\u95ee\u9898\uff0c\u800c\u4e14\u5b50\u95ee\u9898\u7684\u89e3\u6709\u91cd\u590d\u7684\u5730\u65b9\u3002 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : buhi <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u7b97\u6590\u6ce2\u90a3\u5951\u662f O(1), dp \u4e0d\u662f O(1) <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @buhi \u5927\u4f6c\u3002\u6309\u7167\u60a8\u7684\u516c\u5f0f\u7b97\u51fa\u6765 \u7b54\u6848\u4e0d\u5bf9 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @Vegetable \u6211\u9700\u8981\u624b\u52a8\u7b97\u5230 6 \u8fd8\u662f 7 \u554a <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : lxy42 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    “`python
    def walk_dp(n):
    dp = collections.deque([[1, 0, 0], [0, 1, 0], [1, 1, 1]])
    for _ in range(3, n):
    d = [dp[-1][1] + dp[-1][2],
    dp[-2][0] + dp[-2][2],
    dp[-3][0] + dp[-3][1],
    ]
    dp.append(d)
    dp.popleft()
    return sum(dp[-1])
    “` <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @EggtartZ \u60a8\u8fd9\u4e2a m \u662f\u5565\uff1f <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @lxy42 \u5927\u4f6c\u3002\u60a8\u8fd9\u4e2a\u4ece 4 \u5f00\u59cb\u90fd\u662f 3 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : levelworm <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u8fd9\u4e2a\u611f\u89c9\u548c\u5206\u786c\u5e01\u6709\u70b9\u50cf\uff0c\u603b\u5171 X \u7f8e\u5143\uff0c\u6709 5 \u5206\uff0c\u4e00\u6bdb\uff0c25 \u5206\uff0c50 \u5206\u4ee5\u53ca\u4e00\u7f8e\u5143\uff0c\u6c42\u95ee\u603b\u5171\u6709\u51e0\u79cd\u5206\u6cd5\u3002SICP \u4e0a\u7b2c\u4e00\u7ae0\u6709\u7b54\u6848\u3002 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : levelworm <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u6211\u76f4\u63a5\u6284\u4e66\uff0c\u6211\u8ba4\u4e3a\u8fd9\u4e2a\u5206\u786c\u5e01\u548c\u4e0a\u68af\u662f\u4e00\u4e2a\u4e8b\u60c5\u3002<\/p>\n

    they are calculating the number (N) of ways of change a quatity (A) using K kinds of coins by adding:<\/p>\n

    1. the number of ways (X) of changing A without coins of the first type.<\/p>\n

    2.The number of ways (Y) of changing (A – D), where D is the denomination of the fisrt coin, using ALL K types of coins. <\/p><\/div>\n<\/p><\/div>\n<\/li>\n

  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @levelworm \u8fd9\u4e2a\u76f8\u4f3c\u7684\u9898\uff0c\u6211\u90fd\u662f\u770b\u5230\u4e86\u3002\u5230\u73b0\u5728\u6211\u5c31\u4e0d\u660e\u767d\u662f\u5728 \u600e\u4e48\u624d\u80fd\u505a\u5230\u4e0d\u91cd\u590d\u3002 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : EggtartZ <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @hejw19970413 m \u662f\u6bcf\u6b21\u6700\u591a\u8d70\u7684\u53f0\u9636\u6570\uff0c3 \u5c31\u662f\u6bcf\u6b21\u80fd\u8d70 1\uff0c2 \u6216 3 \u683c <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @EggtartZ \u4f60\u8fd9\u4e2a\u597d\u50cf\u662f\u5bf9\u7684\u8036 \uff01\u5389\u5bb3\u4e86 \u6211\u7684\u54e5 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : freemon <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u539f\u9898\u6bd4\u8f83\u7b80\u5355\u54c8\uff0c\u53d8\u5f02\u4e4b\u540e\u7528 dp \u5c31\u597d
    \u5b9a\u4e49 s[i][k] \u4e3a\u5230\u8fbe\u5730 i \u5c42\u9636\u68af\u4e14\u6700\u540e\u4e00\u6b65\u8d70 k \u6b65\u7684 \u8d70\u6cd5\u6570\u91cf
    \u5219
    s[i][1] = s[i-1][2]+s[i-2][3]
    s[i][2] = s[i-2][1]+s[i-2][3]
    s[i][3] = s[i-3][1]+s[i-3][2]<\/p>\n

    \u786e\u5b9a\u4e00\u4e0b\u521d\u59cb\u503c\uff0c\u7136\u540e\u8ba1\u7b97 result = s[n][1]+s[n][2]+s[n][3] \u5373\u53ef \uff1f <\/p><\/div>\n<\/p><\/div>\n<\/li>\n

  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : buhi <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    f(n) = f(n-1) + f(n-2) + f(n-3), \u6c42 f(n), \u8fd9\u4e2a\u5b58\u5728 O(1)\u7684\u89e3\u6cd5.
    https:\/\/www.fq.math.ca\/Scanned\/20-2\/spickerman.pdf
    (\u5c31\u662f\u6d6e\u70b9\u6570\u8ba1\u7b97\u7684\u8bdd, \u53f0\u9636\u6570\u9ad8\u4e86\u4e4b\u540e\u5c31\u8bef\u5dee\u5f88\u5927\u4e86) <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @buhi \u54e5\u4f60\u8fd9\u4e2a\u6211\u6709\u70b9\u6655 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : hejw19970413 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @freemon \u597d \u6211\u7406\u89e3\u4e0b <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : Vegetable <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    @hejw19970413 #29 \u6211\u90a3\u4e2a\u601d\u8def\u51cf\u9519\u5566 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : lylsh1993 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    #30 \u6b63\u89e3 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : yt1523102 <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u5173\u952e\u5b57 \u201c\u591a\u5c11\u79cd\u201d \u8fd9\u79cd\u8981\u7528\u52a8\u6001\u89c4\u5212\u533a\u60f3\u4e86 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : pangleon <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u8fd9\u9053\u9898\u597d\u505a\u5c31\u662f\u600e\u4e48\u80fd\u4e0d\u62a5\u9519\uff0c\u7528\u8fed\u4ee3\u52a0\u5907\u5fd8\u5f55\u4e00\u6837\u4f1a stackoverflow <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : BBCCBB <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u5144\u5f1f, \u6590\u6ce2\u6570\u5217 <\/p>\n

    \u4f60\u767e\u5ea6\u4e00\u4e0b\u4e00\u5806. \u6bd4\u5728 v \u7ad9\u95ee\u9ad8\u6548\u554a. <\/p><\/div>\n<\/p><\/div>\n<\/li>\n

  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : BBCCBB <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u800c\u4e14\u8fd9\u79cd leetcode \u7684\u9898\u4e00\u641c\u4e5f\u662f\u4e00\u5806\u601d\u8def\u89e3\u6790. \u591a\u5237\u5237,\u591a\u7406\u89e3\u4f60\u5c31\u6709\u611f\u89c9\u4e86 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : octobered <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    \u9762\u7ecf\u9898\u719f\u8138\u4e86…. \u4eca\u5e74\u6700\u5c11\u88ab\u95ee\u4e86\u4e09\u6b21\u8fd9\u9053\u9898\u4e86 \u6590\u6ce2\u90a3\u5951\u5b8c\u4e8b <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
    \u8cc7\u6df1\u5927\u4f6c : nznd <\/span> <\/div>\n
    <\/i> <\/span> <\/div>\n<\/p><\/div>\n
    “`python
    if n==1:
    return 1
    first,second=1,2
    for _ in range(3,n+1):
    first,second=second,first+second
    return second
    “`
    \u4e00\u4e2a \u7a7a\u95f4 o(1) \u65f6\u95f4 o(n)\u7684\u89e3\u6cd5(\u7b80\u5355\u6613\u61c2 <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n","protected":false},"excerpt":{"rendered":"

    \u6211\u60f3\u95ee\u4e00\u9053 LeetCode \u53d8\u5f62…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/124938"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=124938"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/124938\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=124938"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=124938"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=124938"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}