Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commit3e7d29f

Browse files
Clarify definition of opt(i, j): choose maximum k among optimal candidates
# Clarify definition of `opt(i, j)` to specify maximum `k` among optimal candidates## DescriptionThis PR updates the documentation to clarify the definition of `opt(i, j)`:- Previously, it was ambiguous when multiple values of `k` achieved the optimum. - The reference explicitly states that we should take the **maximum** value of `k` among all optimal candidates. - This change makes the intended behavior explicit and avoids confusion in implementations. ## MotivationClarifying this definition ensures consistency with the reference and prevents misinterpretation when different values of `k` yield the same optimum. ## Changes- Clarified wording in `opt(i, j)` definition. - Specified that the chosen `k` must be the maximum among all optimal candidates. > The reference ishttps://dl.acm.org/doi/pdf/10.1145/800141.804691, specifically, when we define $K_c$ on the left column.
1 parentda9e74b commit3e7d29f

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

‎src/dynamic_programming/knuth-optimization.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ The Speedup is applied for transitions of the form
1313

1414
$$dp(i, j) = \min_{i \leq k < j} [ dp(i, k) + dp(k+1, j) + C(i, j) ].$$
1515

16-
Similar to[divide and conquer DP](./divide-and-conquer-dp.md), let $opt(i, j)$ be the value of $k$ that minimizes the expression in the transition ($opt$ is referred to as the "optimal splitting point" further in this article). The optimization requires that the following holds:
16+
Similar to[divide and conquer DP](./divide-and-conquer-dp.md), let $opt(i, j)$ be themaximumvalue of $k$ that minimizes the expression in the transition ($opt$ is referred to as the "optimal splitting point" further in this article). The optimization requires that the following holds:
1717

1818
$$opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j).$$
1919

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp