题目描述：扔n个骰子，求点数之和为s的概率
思路：一共有6^n种可能，dp求出扔n个骰子时出现各种点数的次数
public static double getResult(int n,int s) { double divide = Math.pow(6,n); int sum = 6*n; int[][] dp = new int[n+1][sum+1]; for(int i = 1;i<=6;i++){ dp[1][i] = 1; } for(int i = 2;i<=n;i++){ for (int j = i;j<=i*6;j++) { for (int k=1;k<=j && k<=6;k++) { dp[i][j]+=dp[i-1][j-k]; } } } return dp[n][s]/divide; }优化思路：其实dp[i]只会用到dp[i-1]，所以考虑旋转数组优化空间复杂度
public static double getResult2(int n, int s) { double divide = Math.pow(6, n); int sum = 6 * n; int[][] dp = new int[2][sum + 1]; boolean flag = false; for (int i = 1; i <= 6; i++) { dp[0][i] = 1; } int cur = 1; int other = 0; for (int i = 2; i <= n; i++) { flag = i % 2 == 0; cur = flag ? 1 : 0; other = 1 - cur; for (int j = i; j <= i * 6; j++) { for (int k = 1; k <= j && k <= 6; k++) { dp[cur][j] += dp[other][j - k]; } } Arrays.fill(dp[other], 0); } return dp[cur][s] / divide; }