Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit d7a84e8

Browse filesBrowse files
simonyanliadamant-pwn
authored andcommitted
Update divide-and-conquer-dp.md
typo, quadrangle was spelled "qudrangle"
1 parent 61d8edb commit d7a84e8
Copy full SHA for d7a84e8

File tree

Expand file treeCollapse file tree

1 file changed

+1
-1
lines changed
Filter options
Expand file treeCollapse file tree

1 file changed

+1
-1
lines changed

‎src/dynamic_programming/divide-and-conquer-dp.md

Copy file name to clipboardExpand all lines: src/dynamic_programming/divide-and-conquer-dp.md
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,7 @@ time. Then the straightforward evaluation of the above recurrence is $O(m n^2)$.
2121
are $m \times n$ states, and $n$ transitions for each state.
2222

2323
Let $opt(i, j)$ be the value of $k$ that minimizes the above expression. Assuming that the
24-
cost function satisfies the qudrangle inequality, we can show that
24+
cost function satisfies the quadrangle inequality, we can show that
2525
$opt(i, j) \leq opt(i, j + 1)$ for all $i, j$. This is known as the _monotonicity condition_.
2626
Then, we can apply divide and conquer DP. The optimal
2727
"splitting point" for a fixed $i$ increases as $j$ increases.

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.