https://blog.pythonwood.com/人生苦短，我用PythonSat, 16 Dec 2017 16:30:00 +0800https://blog.pythonwood.com/2017/12/%E5%A8%81%E4%BD%90%E5%A4%AB%E5%8D%9A%E5%BC%88%EF%BC%9A%E5%8F%96%E7%9F%B3%E5%AD%90%E6%B8%B8%E6%88%8F%E7%AE%97%E6%B3%95%E2%80%94%E2%80%94%E6%8C%91%E6%88%98PythonTip/<p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目，如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="取石子游戏">取石子游戏</a>，如今积累工作经验之后从新挑战，成功了。把过程记录分享下。</p> <h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法， 一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。 现在给出初始的两堆石子的数目a和b，如果轮到你先取，假设双方都采取最好的策略 …</p>pythonwoodSat, 16 Dec 2017 16:30:00 +0800tag:blog.pythonwood.com,2017-12-16:/2017/12/威佐夫博弈：取石子游戏算法——挑战PythonTip/python算法pythontip动态规划https://blog.pythonwood.com/2014/08/%E3%80%90%E5%AE%9E%E4%B9%A0%E8%AE%B0%E3%80%912014-08-29%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0Boyer-Moore%E5%92%8C%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2%EF%BC%88LCS%EF%BC%89%E9%97%AE%E9%A2%98%E2%80%94%E2%80%94%E9%98%BF%E9%87%8C%E6%A0%A1%E6%8B%9B%E9%A2%98/<!-- 昨天的问题 方案一：寻找hash函数，可行性极低。 方案二：载入内存，维护成一个守护进程的服务。难度比较大。 方案三：使用前5位来索引，由前3位增至前5位唯一性，理论上是分拆记录扩大100倍，但可以就地利用mysql，最易行。 方案四：使用方案三，但增加一个表以减少冗余，但代价新开一个表，并且每次查询都select join两个表。 --> <h3 id="_1">最长公共子串问题分析<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>其实这是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧：&rdquo;bab&rdquo;和&rdquo;caba&rdquo;(当然我们现在一眼就可以看出来最长公共子串是&rdquo;ba&rdquo;或&rdquo;ab&rdquo;)</p> <p>b　　a　　b</p> <p>c　　0　　0　　0 …</p>pythonwoodFri, 29 Aug 2014 21:23:00 +0800tag:blog.pythonwood.com,2014-08-29:/2014/08/【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）问题——阿里校招题/阿里校招实习算法最长公共子串字符串动态规划