Update Readme.md

wisdompeak · web-flow · commit 4c4e548a2b03 · 2022-02-24T22:03:03.000-08:00
diff --git a/Dynamic_Programming/376.Wiggle-Subsequence/Readme.md b/Dynamic_Programming/376.Wiggle-Subsequence/Readme.md
@@ -26,11 +26,15 @@
 
 #### &#35299;&#27861;2&#65306;DP
 
-&#35774;&#35745;&#20004;&#20010;&#29366;&#24577;&#21464;&#37327;&#65306;p&#34920;&#31034;&#25130;&#27490;&#30446;&#21069;&#20026;&#27490;&#65292;&#26368;&#21518;&#19968;&#20010;&#20803;&#32032;&#26159;&#19978;&#21319;&#36235;&#21183;&#30340;&#26368;&#38271;wiggle&#23376;&#24207;&#21015;&#65307;q&#34920;&#31034;&#25130;&#27490;&#30446;&#21069;&#20026;&#27490;&#65292;&#26368;&#21518;&#19968;&#20010;&#20803;&#32032;&#26102;&#19979;&#38477;&#36235;&#21183;&#30340;&#26368;&#38271;wiggle&#23376;&#24207;&#21015;&#12290;
+&#35774;&#35745;&#20004;&#20010;&#29366;&#24577;&#21464;&#37327;&#65306;p&#34920;&#31034;&#25130;&#27490;&#30446;&#21069;&#20026;&#27490;&#65292;&#26368;&#21518;&#19968;&#20010;&#20803;&#32032;&#26159;&#19978;&#21319;&#36235;&#21183;&#30340;&#26368;&#38271;wiggle&#23376;&#24207;&#21015;&#65307;q&#34920;&#31034;&#25130;&#27490;&#30446;&#21069;&#20026;&#27490;&#65292;&#26368;&#21518;&#19968;&#20010;&#20803;&#32032;&#26159;&#19979;&#38477;&#36235;&#21183;&#30340;&#26368;&#38271;wiggle&#23376;&#24207;&#21015;&#12290;
 
-&#27599;&#26597;&#30475;&#19968;&#20010;&#25968;&#23383;&#65292;&#23581;&#35797;&#26356;&#26032;&#20004;&#20010;&#21464;&#37327;p&#21644;q&#12290;&#24403;nums[i]&#27604;nums[i-1]&#22823;&#26102;&#65292;&#24847;&#21619;&#30528;q&#23545;&#24212;&#30340;&#24207;&#21015;&#20043;&#21518;&#21448;&#20986;&#29616;&#20102;&#19968;&#20010;&#19978;&#21319;&#27573;&#65292;&#35828;&#26126;&#21487;&#20197;&#26356;&#26032;p&#65292;&#21363;p=q+1&#12290;&#24403;nums[i]&#27604;nums[i-1]&#23567;&#26102;&#65292;&#24847;&#21619;&#30528;p&#23545;&#24212;&#30340;&#24207;&#21015;&#20043;&#21518;&#21448;&#20986;&#29616;&#20102;&#19968;&#20010;&#19979;&#38477;&#27573;&#65292;&#35828;&#26126;&#21487;&#20197;&#26356;&#26032;q&#65292;&#21363;p=q+1
+&#39318;&#20808;&#25105;&#20204;&#35201;&#26377;&#36825;&#26679;&#19968;&#20010;&#27010;&#24565;&#12290;&#26080;&#35770;&#24403;&#21069;&#20803;&#32032;x&#26159;&#20160;&#20040;&#65292;p&#24207;&#21015;&#30340;&#26368;&#21518;&#19968;&#20010;&#20803;&#32032;&#35201;&#20040;&#26159;x&#65292;&#35201;&#20040;&#21482;&#33021;&#26159;&#22312;x&#21069;&#38754;&#12289;&#20294;&#26159;&#27604;x&#22823;&#30340;&#20803;&#32032;&#12290;&#21453;&#35777;&#65306;&#22914;&#26524;&#23384;&#22312;&#19968;&#20010;&#20803;&#32032;y&#22312;x&#21069;&#38754;&#12289;&#19988;&#27604;x&#35201;&#23567;&#65292;&#37027;&#20040;&#36825;&#20010;&#23558;y&#20174;p&#24207;&#21015;&#30340;&#32467;&#23614;&#37324;&#21435;&#25481;&#12289;&#25913;&#25104;x&#21152;&#20837;p&#24207;&#21015;&#30340;&#32467;&#23614;&#65292;&#21516;&#26679;&#19981;&#24433;&#21709;p&#24207;&#21015;&#30340;&#24615;&#36136;&#21644;&#38271;&#24230;&#12290;&#21516;&#29702;&#65292;&#26080;&#35770;&#24403;&#21069;&#20803;&#32032;x&#26159;&#20160;&#20040;&#65292;q&#24207;&#21015;&#30340;&#26368;&#21518;&#19968;&#20010;&#20803;&#32032;&#35201;&#20040;&#26159;x&#65292;&#35201;&#20040;&#21482;&#33021;&#26159;&#22312;x&#21069;&#38754;&#12289;&#20294;&#26159;&#27604;x&#23567;&#30340;&#20803;&#32032;&#12290;
+
+&#22238;&#21040;&#25105;&#20204;&#30340;&#38382;&#39064;&#12290;&#25105;&#20204;&#27599;&#26597;&#30475;&#19968;&#20010;&#25968;&#23383;&#65292;&#23581;&#35797;&#26356;&#26032;&#20004;&#20010;&#21464;&#37327;p&#21644;q&#12290;&#24403;nums[i]>nums[i-1]&#22823;&#26102;&#65292;&#30001;&#21069;&#38754;&#21487;&#30693;&#65292;&#21407;&#20808;q&#24207;&#21015;&#30340;&#32467;&#23614;&#20803;&#32032;&#19968;&#23450;&#27604;nums[i]&#23567;&#65292;&#20110;&#26159;&#20877;&#25509;&#19978;nums[i]&#30340;&#35805;q&#24207;&#21015;&#19968;&#23450;&#19981;&#20250;&#21464;&#30340;&#26356;&#38271;&#12290;&#21516;&#26102;&#65292;&#21407;&#20808;q&#24207;&#21015;&#30340;&#32467;&#23614;&#19968;&#23450;&#27604;nums[i]&#23567;&#65292;&#25509;&#19978;nums[i]&#20043;&#21518;&#65292;&#23601;&#21487;&#20197;&#24471;&#21040;&#19968;&#20010;&#26032;&#30340;p&#30340;&#24207;&#21015;&#12290;&#25925;&#26377;```q&#19981;&#21464;&#65292;p=q+1```.
+
+&#31867;&#20284;&#22320;&#65292;&#24403;nums[i]<nums[i-1]&#23567;&#26102;&#65292;&#30001;&#21069;&#38754;&#21487;&#30693;&#65292;&#21407;&#20808;p&#24207;&#21015;&#30340;&#32467;&#23614;&#20803;&#32032;&#19968;&#23450;&#27604;nums[i]&#22823;&#65292;&#20110;&#26159;&#20877;&#25509;&#19978;nums[i]&#30340;&#35805;p&#24207;&#21015;&#19968;&#23450;&#19981;&#20250;&#21464;&#30340;&#26356;&#38271;&#12290;&#21516;&#26102;&#65292;&#21407;&#20808;p&#24207;&#21015;&#30340;&#32467;&#23614;&#19968;&#23450;&#27604;nums[i]&#22823;&#65292;&#25509;&#19978;nums[i]&#20043;&#21518;&#65292;&#23601;&#21487;&#20197;&#24471;&#21040;&#19968;&#20010;&#26032;&#30340;q&#30340;&#24207;&#21015;&#12290;&#25925;&#26377;```p&#19981;&#21464;&#65292;q=p+1```.
 
 &#22240;&#20026;&#26080;&#27861;&#30830;&#23450;&#26368;&#38271;wiggle&#24207;&#21015;&#30340;&#26368;&#21518;&#19968;&#27573;&#26159;&#19978;&#21319;&#36824;&#26159;&#19979;&#38477;&#65292;&#22240;&#27492;&#26368;&#21518;&#30340;&#31572;&#26696;&#26159;&#22312;p&#21644;q&#20043;&#38388;&#36873;&#26368;&#22823;&#20540;&#12290;
 
 
-[Leetcode Link](https://leetcode.com/problems/wiggle-subsequence)
+[Leetcode Link](https://leetcode.com/problems/wiggle-subsequence)

-Original file line number
+Diff line change
 #### 解法2：DP
 -设计两个状态变量：p表示截止目前为止，最后一个元素是上升趋势的最长wiggle子序列；q表示截止目前为止，最后一个元素时下降趋势的最长wiggle子序列。
 +设计两个状态变量：p表示截止目前为止，最后一个元素是上升趋势的最长wiggle子序列；q表示截止目前为止，最后一个元素是下降趋势的最长wiggle子序列。
 -每查看一个数字，尝试更新两个变量p和q。当nums[i]比nums[i-1]大时，意味着q对应的序列之后又出现了一个上升段，说明可以更新p，即p=q+1。当nums[i]比nums[i-1]小时，意味着p对应的序列之后又出现了一个下降段，说明可以更新q，即p=q+1
 +首先我们要有这样一个概念。无论当前元素x是什么，p序列的最后一个元素要么是x，要么只能是在x前面、但是比x大的元素。反证：如果存在一个元素y在x前面、且比x要小，那么这个将y从p序列的结尾里去掉、改成x加入p序列的结尾，同样不影响p序列的性质和长度。同理，无论当前元素x是什么，q序列的最后一个元素要么是x，要么只能是在x前面、但是比x小的元素。
++
 +回到我们的问题。我们每查看一个数字，尝试更新两个变量p和q。当nums[i]>nums[i-1]大时，由前面可知，原先q序列的结尾元素一定比nums[i]小，于是再接上nums[i]的话q序列一定不会变的更长。同时，原先q序列的结尾一定比nums[i]小，接上nums[i]之后，就可以得到一个新的p的序列。故有```q不变，p=q+1```.
++
 +类似地，当nums[i]<nums[i-1]小时，由前面可知，原先p序列的结尾元素一定比nums[i]大，于是再接上nums[i]的话p序列一定不会变的更长。同时，原先p序列的结尾一定比nums[i]大，接上nums[i]之后，就可以得到一个新的q的序列。故有```p不变，q=p+1```.
 因为无法确定最长wiggle序列的最后一段是上升还是下降，因此最后的答案是在p和q之间选最大值。
 -[Leetcode Link](https://leetcode.com/problems/wiggle-subsequence)
 +[Leetcode Link](https://leetcode.com/problems/wiggle-subsequence)