dices_sum.py

# -*- 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