力扣500题刷题笔记8：前缀枚举与n个骰子点数概率计算

力扣500题刷题笔记8包含两个具体题目的解题思路和方法。第一个题目是要构造一个函数 f(prefix, n)，来求出1~n中有多少个数的前缀是prefix。解题方法是最终答案的前缀开始枚举，不断减小k值，一位一位来看答。第二个题目是剑指 Offer 60中的问题，即求n个骰子扔在地上，所有骰子朝上一面的点数之和为s。解题思路是用动态规划来计算所有点数出现的概率。具体做法是先计算所有点数出现的总次数，然后使用状态表示f[i][j]来表示投掷i个骰子，点数之和为j出现的次数。计算时依据最后一次投掷的点数划分集合，即f[i][j] = f[i-1][j-k]，k属于{1, 2, 3, 4, 5, 6}并且j>=k。最后是对数组进行初始化，投掷0个骰子，点数之和为0只有一种方案。最终输出的是包含所有点数的概率数组。 This summary covers two specific problems and solutions from the LeetCode 500 problem-solving notes. The first problem is to construct a function f(prefix, n) to find out how many numbers in the range of 1 to n have the prefix "prefix". The solution method involves enumerating the prefix of the final answer and continuously reducing the value of k to examine the answer digit by digit. The second problem is from the Sword Point Offer 60, which involves throwing n dice on the ground and finding the probability distribution of the sum of the points. The solution approach uses dynamic programming to calculate the probability of all point values. It begins by calculating the total number of occurrences of all point values and then uses the state representation f[i][j] to denote the number of occurrences when throwing i dice with a sum of j. The calculation revolves around dividing the set based on the last dice throw, namely f[i][j] = f[i-1][j-k], where k belongs to {1, 2, 3, 4, 5, 6} and j>=k. Initialization involves setting f[1][1,2,3,4,5,6] = 1 = f[0][0], as there is only one way of getting a sum of 0 when throwing 0 dice. The final output is an array containing the probability of all point values.