1223. 掷骰子模拟 范围DP

1223. 掷骰子模拟 范围DP

做题结果

失败，这个类型的dp感觉特别难，写了几次都找不到感觉，数学基础可能比较重要

方法：动态规划

参考：​​假设前面的数量元素个数不足，是无需处理的，直接把前面所有结果抛到1到6的累加

2. 假设刚好踩到限制边缘，比如规定只能有3个3，现在刚好是4个数，那就刨除第一位是3 的情况，3 3 3 3

3. 假设有5个数， b a 3 3 3， 那么a可以是其他任意一个数字，但是不能是3，在a不是3的情况，推到到第一个3，才能正确进行刨除，因为只有这种情况，a 3 3 3,中第一个3才能保证是第一个，任意非3数字后面加个3，才可以保证这个3是此连续段的第一个3，注意我们不能直接从第一个3开始推，因为这个和有可能包含这个3是第一个，第二个3的情况，这些情况是合法的。所以这个部分需要再前面一个数非3的和推导出来。

class Solution { public int dieSimulator(int n, int[] rollMax) { long MOD = (long) (1e9+7); long[][] dp = new long[n+1][6]; Arrays.fill(dp[1],1); for(int i = 2; i <= n; i++){ for(int j=0; j < 6; j++){ for(int k = 0; k < 6; k++){ dp[i][j] = (dp[i][j]+dp[i-1][k])%MOD; } if(i-rollMax[j]-1==0){ --dp[i][j]; }else if(i-rollMax[j]-1>0){ for(int k = 0; k < 6; k++){ if(k!=j){ dp[i][j] = (dp[i][j]-dp[i-rollMax[j]-1][k]+MOD)%MOD; } } } } } long sum = 0; for(int i = 0; i < 6; i++){ sum += dp[n][i]; sum = sum %MOD; } return (int)sum; } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。