骰子抛掷概率计算：动态规划与重复子问题

\u7ed9\u4f60 n \u4e2a\u9274\u5b50\uff0c\u6bcf\u4e2a\u9274\u5b50\u6709 Ai \u9762\uff0c\u6240\u6709\u9274\u5b50\u540c\u65f6\u6295\u51fa\uff0c\u95ee\u6700\u540e\u80fd\u9009\u51fa\u548c\u4e3a 10 \u7684\u9274\u5b50\u6982\u7387\u3002\u4e2d\u8ba1\u6570\u7c7b\u52a8\u6001\u8ba1\u5212\u4e3a\u4ec0\u4e48\u4f1a\u91cd\uff0c\u662f\u56e0\u4e3a\u5728\u8ba1\u7b97\u7684\u8fc7\u7a0b\u4e2d\uff0c\u5b58\u5728\u91cd\u590d\u7684\u5b50\u95ee\u9898\u3002\n\n\u5728\u672c\u9898\u4e2d\uff0c\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u52a8\u6001\u8ba1\u5212\u6765\u89e3\u51b3\u3002\u6211\u4eec\u5b9a\u4e49\u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4 dp[i][j] \u8868\u793a\u524d i \u4e2a\u9274\u5b50\u4e2d\uff0c\u9009\u51fa\u548c\u4e3a j \u7684\u6982\u7387\u3002\u521d\u59cb\u5316\u65f6\uff0c\u2002dp[0][0] \u2002= 1\uff0c\u5176\u5b83\u4f4d\u7f6e\u90fd\u4e3a 0\u3002\n\n\u7136\u540e\u6211\u4eec\u5f00\u59cb\u9010\u4e2a\u8ba1\u7b97 dp[i][j]\u3002\u5bf9\u4e8e\u7b2c i \u4e2a\u9274\u5b50\uff0c\u5b83\u6709 Ai \u9762\uff0c\u5206\u522b\u4e3a 1 \u5230 Ai\u3002\u6211\u4eec\u53ef\u4ee5\u9010\u4e2a\u5386\u6d4b\u8fd9 Ai \u4e2a\u9762\uff0c\u5bf9\u6bcf\u4e2a\u9762\u7684\u503c k\uff0c\u66f4\u65b0 dp[i][j] \u2002= dp[i][j] \u2002+ dp[i-1][j-k]\u3002\n\n\u901a\u8fc7\u8fd9\u6837\u7684\u66f4\u65b0\u65b9\u5f0f\uff0c\u6211\u4eec\u53ef\u4ee5\u8ba1\u7b97\u51fa\u6700\u540e\u7684 dp[n][10]\uff0c\u5373\u524d n \u4e2a\u9274\u5b50\u9009\u51fa\u548c\u4e3a 10 \u7684\u6982\u7387\u3002\n\n\u5374\u662f\uff0c\u7531\u4e8e\u6211\u4eec\u7684\u66f4\u65b0\u65b9\u5f0f\u662f\u901a\u8fc7\u5386\u6d4b\u7b2c i \u4e2a\u9274\u5b50\u7684\u6bcf\u4e2a\u9762\u7684\u503c k\uff0c\u7136\u540e\u66f4\u65b0 dp[i][j] \u2002= dp[i][j] \u2002+ dp[i-1][j-k]\u3002\u8fd9\u5bfc\u81f4\u4e86\u91cd\u590d\u8ba1\u7b97\u3002\u56e0\u4e3a\u5728\u8ba1\u7b97 dp[i][j] \u65f6\uff0c\u6211\u4eec\u5df2\u7ecf\u8ba1\u7b97\u4e86\u524d i-1 \u4e2a\u9274\u5b50\u4e2d\u9009\u51fa\u548c\u4e3a j-k \u7684\u6982\u7387\uff0c\u800c\u5728\u8ba1\u7b97 dp[i][j+1] \u65f6\uff0c\u6211\u4eec\u53c8\u4f1a\u8ba1\u7b97\u524d i-1 \u4e2a\u9274\u5b50\u4e2d\u9009\u51fa\u548c\u4e3a j-k \u7684\u6982\u7387\u3002\n\n\u6240\u4ee5\uff0c\u4e2d\u8ba1\u6570\u7c7b\u52a8\u6001\u8ba1\u5212\u4f1a\u91cd\uff0c\u9700\u8981\u901a\u8fc7\u4e00\u4e9b\u65b9\u6cd5\u6765\u907f\u514d\u91cd\u590d\u8ba1\u7b97\uff0c\u4f8b\u5982\u4f7f\u7528\u8bb0\u5fc6\u5316\u641c\u7d22\u6216\u8005\u4f18\u5316\u66f4\u65b0\u65b9\u5f0f\u3002