From 915b569dfda3cab8c022b4e8e1fbace3158a4b30 Mon Sep 17 00:00:00 2001
From: Trisolaris HD <36555123+TrisolarisHD@users.noreply.github.com>
Date: Sat, 30 Mar 2019 21:02:07 +0800
Subject: [PATCH] Update state-optimization.md (#1126)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

做了一些奇怪的修改. fix #1090
---
 docs/dp/optimizations/state-optimization.md | 26 ++++++++++++--------------
 1 file changed, 12 insertions(+), 14 deletions(-)

diff --git a/docs/dp/optimizations/state-optimization.md b/docs/dp/optimizations/state-optimization.md
index 2bc9802f..58e72e51 100644
--- a/docs/dp/optimizations/state-optimization.md
+++ b/docs/dp/optimizations/state-optimization.md
@@ -14,25 +14,25 @@
 
 您一眼秒了它，这不是板子吗？
 
-定义状态 $dp_{i,j}$ 为 $A$ 的前 $i$ 位与 $B$ 的前 $j$ 位最长公共子串，则有
+定义状态 $f_{i,j}$ 为 $A$ 的前 $i$ 位与 $B$ 的前 $j$ 位最长公共子串，则有
 
 $$
-dp_{i,j}=
+f_{i,j}=
 \begin{cases}
-\max(dp_{i-1,j},dp_{i,j-1}) & ,A_i \neq B_j \\
-dp_{i-1,j-1}+1 & ,A_i = B_j 
+\max(f_{i-1,j},f_{i,j-1}) & ,A_i \neq B_j \\
+f_{i-1,j-1}+1 & ,A_i = B_j 
 \end{cases}
 $$
 
 上述做法的时间复杂度 $O(nm)$，无法通过本题。
 
-### Higher solution
+### Better solution
 
 我们仔细一想，发现了一个性质：最终答案不会超过 $m$。
 
 我们又仔细一想，发现 LCS 满足贪心的性质。
 
-更改状态定义 $dp_{i,j}$ 为与 $B$ 前 $i$ 位的最长公共子序列长度为 $j$ 的 $A$ 的最短前缀长度（即将朴素做法的答案与第一维状态对调）
+更改状态定义 $f_{i,j}$ 为与 $B$ 前 $i$ 位的最长公共子序列长度为 $j$ 的 $A$ 的最短前缀长度（即将朴素做法的答案与第一维状态对调）
 
 可以通过预处理 $A$ 的每一位的下一个 $a,b,\cdots,z$ 的出现位置进行 $O(1)$ 的顺推转移。
 
@@ -42,26 +42,24 @@ $$
 
 ### Problem
 
-给定一个 $N$ 个点的无权有向图，判断该图是否存在哈密顿回路。$(2\le N\le 20)$
+给定一个 $n$ 个点的无权有向图，判断该图是否存在哈密顿回路。$(2\le n\le 20)$
 
 ### Naive solution
 
 看到数据范围，我们考虑状压。
 
-设 $dp_{st,i}$ 表示从 $1$ 出发，经过点集 $st$ 后到达 $i$ 的方案是否存在。则有
+设 $f_{s,i}$ 表示从点 $1$ 出发，仅经过点集 $s$ 中的点能否到达点 $i$。记 $g$ 为原图的邻接矩阵。则有
 
 $$
-dp_{st,i}=\sum dp_{st-2^{i-1},j}\&mp_{j,i}\;\;(st\&2^{i-1} \;\&\&\; st\&2^{j-1})
+f_{s, i} = \bigcap_{j\in s, j\neq i}f_{s - \left\{i\right\}, j}\cap g_{j, i} \left(i\in s\right)
 $$
 
-其中 $mp$ 为图的邻接矩阵
-
 时间复杂度 $O(n^2 \times 2^n)$，写得好看或许能过，但是并不优美。
 
-### Higher solution
+### Better solution
 
 上面的状态设计中，每个 $dp$ 值只代表一个 `bool` 值，这让我们觉得有些浪费。
 
-我们可以考虑对于每个状态 $st$ 将 $dp_{st,1 \cdots n}$ 压成一个 `int`，发现我们可以将邻接矩阵同样压缩后进行 $O(1)$ 转移。
+我们可以考虑对于每个状态 $s$ 将 $f_{s,1},f_{s,2},\dots,f_{s,n}$ 压成一个 `int`，发现我们可以将邻接矩阵同样压缩后进行 $O(1)$ 转移。
 
-时间复杂度 $O(n\times 2^n)$ ,可以稳过这道题。
+时间复杂度 $O(n\times 2^n)$ ,可以通过这道题。
-- 
2.11.0