骰子求和

yingl · yingl · commit 4ba94813bcc1 · 2016-09-05T16:19:42.000+08:00
diff --git a/dices_sum.py b/dices_sum.py
@@ -0,0 +1,31 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param {int} n an integer
+    # @return {tuple[]} a list of tuple(sum, probability)
+    def dicesSum(self, n):
+        # Write your code here
+        '''
+        只有1个骰子，概率是1/6。
+        对于有2个骰子的情况，以第一个骰子为基础算，m[x][y]代表x个骰子获得y点。
+        m[2][7]等于以下状态的和：
+        - m[1][1] / 6（出6点）
+        - m[1][2] / 6（出5点）
+        - m[1][3] / 6（出4点）
+        - m[1][4] / 6（出3点）
+        - m[1][5] / 6（出2点）
+        - m[1][6] / 6（出1点）
+        '''
+        ret = []
+        matrix = [[0] * (n * 6) for i in xrange(n)]
+        for i in xrange(6): # 初始化1个骰子的结果
+            matrix[0][i] = 1.0 / 6.0
+        for i in xrange(n - 1):
+            for j in xrange(i, (i + 1) * 6):
+                prob = matrix[i][j] / 6
+                for k in xrange(1, 7):
+                  # 利用matrx[i][j]更新matrix[i + 1][j + k]
+                  matrix[i + 1][j + k] += prob
+        for i in xrange(n - 1, n * 6):
+            ret.append([i + 1, matrix[-1][i]])
+        return ret
