Skip to content

Instantly share code, notes, and snippets.

@diegozeng
Created January 22, 2016 07:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save diegozeng/6c964f623bbeaa716526 to your computer and use it in GitHub Desktop.
Save diegozeng/6c964f623bbeaa716526 to your computer and use it in GitHub Desktop.
public class DiceCombination {
int count;
Map<String,Integer> cache = new HashMap<>();
public float sumPossibilityButtomUpDP(int dice, int target) {
int total = (int) Math.pow(6,dice);
int[][] dp = new int[dice+1][target+1];
for(int i = 1; i <= Math.min(target,6); i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= dice; i++)
for (int j = 1; j <= target; j++)
for (int k = 1; k <= 6 && k < j; k++)
dp[i][j] += dp[i-1][j-k];
return (float)dp[dice][target]/total;
}
public float sumPossibilityTopDownDP(int dice, int target) {
int total = (int) Math.pow(6,dice);
int res = helperTopDownDP(target,dice);
return (float)res/total;
}
public int helperTopDownDP(int target, int dice) {
if(dice == 0) {
return target == 0 ? 1:0;
}
if(cache.containsKey(String.valueOf(dice) + "*" + String.valueOf(target))) {
return cache.get(String.valueOf(dice) + "*" + String.valueOf(target));
}
int res = 0;
for(int k = 1; k<=6; k++) {
int tmp = helperTopDownDP(target-k,dice-1);
res+=tmp;
}
cache.put(String.valueOf(dice) + "*" + String.valueOf(target), res);
return res;
}
public float sumPossibility(int dice, int target) {
int total = (int) Math.pow(6,dice);
helper(target,0,dice, 0);
return (float)count/total;
}
public void helper(int target, int trial, int dice, int sum) {
if(trial == dice) {
if(target == sum)
count++;
return;
}
for(int i = 1; i<=6; i++) {
helper(target, trial+1, dice, sum+i);
}
}
public static void main(String[] args) {
DiceCombination dc = new DiceCombination();
System.out.println(dc.sumPossibility(10,35));
System.out.println(dc.sumPossibilityTopDownDP(10,35));
System.out.println(dc.sumPossibilityButtomUpDP(10,35));
}
}
@harrywithcode
Copy link

From Line 26 to Line 40. I don't think cache works. You only need the "result" variable and the program still works.
Since every recursion loop, dice and target are unique than previous, so map.containsKey() branch will never been entered.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment