好难啊，二刷还是不会，Mark https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

1.题目

2.分析

状态表示：dp[i][j] ，表示投掷完i枚骰子后，点数j的出现次数。

初始状态：表示投掷完i枚骰子后,点数和是[1,6]，即dp[1][k]=1；（k从1到6）

找出状态转移方程

3.代码

3.1

class Solution { public double[] twoSum(int n) { int[][] dp=new int[13][70]; for(int i=1;i<=6;i++){ dp[1][i]=1; } for (int i = 2; i <= n; i ++) { //点数范围:[i,6*i] for (int j = i; j <= 6*i; j ++) { //第i枚骰子会出现的六个点数 for (int cur = 1; cur <= 6; cur ++) { if (j - cur <= 0) { break; } dp[i][j] += dp[i-1][j-cur]; } } } double all=Math.pow(6,n);//一共all种结果 double[] ret=new double[6*n-n+1];//结果集 int k=0; //点数范围:[n,6*n] for(int i=n;i<=6*n;i++){ ret[k++]=dp[n][i]*1.0/all; } return ret; } }

3.2 空间优化

从运行结果上没看出节省空间啊，搞不懂。

class Solution { public double[] twoSum(int n) { int[] dp=new int[70]; for (int i = 1; i <= 6; i ++) { dp[i] = 1; } for (int i = 2; i <= n; i ++) { for (int j = 6*i; j >= i; j --) { dp[j] = 0; for (int cur = 1; cur <= 6; cur ++) { if (j - cur < i-1) { break; } dp[j] += dp[j-cur]; } } } //以下同方法一 double all = Math.pow(6, n); double[] ret=new double[6*n-n+1]; int k=0; for (int i = n; i <= 6 * n; i ++) { ret[k++]=(dp[i] * 1.0 / all); } return ret; } }