anxious-coder-lhs
diff --git a/‎slides/dynamicprogramming/tiling_problems.key
34.8 KB b/‎slides/dynamicprogramming/tiling_problems.key
34.8 KB
diff --git a/‎src/main/java/com/williamfiset/algorithms/dp/examples/scenes/Scenes.java
Lines changed: 7 additions & 4 deletions b/‎src/main/java/com/williamfiset/algorithms/dp/examples/scenes/Scenes.java
Lines changed: 7 additions & 4 deletions
@@ -17,8 +17,8 @@ public class Scenes {
   public static void main(String[] args) throws IOException {
     String[] ln = br.readLine().split(" ");
     N = Integer.parseInt(ln[0]); // Total ribbon length
-    W = Integer.parseInt(ln[1]);
-    H = Integer.parseInt(ln[2]);
+    W = Integer.parseInt(ln[1]); // Width
+    H = Integer.parseInt(ln[2]); // Height
 
     solution1();
   }
@@ -51,8 +51,11 @@ static long f(int w, int ribbon) {
     long scenes = 0L;
     // Try placing all possible ribbon lengths at this column/width
     for (int len = 0; len <= H; len++) {
-      scenes = (scenes + f(w + 1, ribbon - len)) % MOD;
+      scenes = (scenes + f(w + 1, ribbon - len));
     }
-    return dp[w][ribbon] = scenes;
+    // Store and return the number of scenes for this sub-problem.
+    // Applying the MOD after the loop is safe since H is at most 100 and
+    // the MOD is 10^9+7 which cannot overflow a signed 64bit integer.
+    return dp[w][ribbon] = scenes % MOD;
   }
 }
Original file line number	Diff line number	Diff line change
`@@ -17,8 +17,8 @@ public class Scenes {`
`17`	`17`	`public static void main(String[] args) throws IOException {`
`18`	`18`	`String[] ln = br.readLine().split(" ");`
`19`	`19`	`N = Integer.parseInt(ln[0]); // Total ribbon length`
`20`		`- W = Integer.parseInt(ln[1]);`
`21`		`- H = Integer.parseInt(ln[2]);`
	`20`	`+ W = Integer.parseInt(ln[1]); // Width`
	`21`	`+ H = Integer.parseInt(ln[2]); // Height`
`22`	`22`
`23`	`23`	`solution1();`
`24`	`24`	`}`
`@@ -51,8 +51,11 @@ static long f(int w, int ribbon) {`
`51`	`51`	`long scenes = 0L;`
`52`	`52`	`// Try placing all possible ribbon lengths at this column/width`
`53`	`53`	`for (int len = 0; len <= H; len++) {`
`54`		`- scenes = (scenes + f(w + 1, ribbon - len)) % MOD;`
	`54`	`+ scenes = (scenes + f(w + 1, ribbon - len));`
`55`	`55`	`}`
`56`		`- return dp[w][ribbon] = scenes;`
	`56`	`+ // Store and return the number of scenes for this sub-problem.`
	`57`	`+ // Applying the MOD after the loop is safe since H is at most 100 and`
	`58`	`+ // the MOD is 10^9+7 which cannot overflow a signed 64bit integer.`
	`59`	`+ return dp[w][ribbon] = scenes % MOD;`
`57`	`60`	`}`
`58`	`61`	`}`