最长回文字符串题解(动态规划)

LeetCode正题Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.ExampleInput: "babad"Output: "bab"Note: "aba" is also a valid answer.ExampleInput: "cbbd"Output: "bb"思考回文字符串即正向顺序和反向顺序的字幕排序是一致的字段串。题的大意为寻找一个指定字符串中的最长的回文字符串。首选,暴力解法需要遍历所有子串并判断子串是否为回文字符串。假设给定字符串长度n,那么子串的总数为​n(n+1)/2(即1 2 3 ... n的和),即需要O(n^2),然后判断每个子串是否为回文字符串的时间复杂度为O(n),即总共需要...阅读全文

最长不重复子字符串问题(动态规划)

问题Given a string, find the length of the longest substring without repeating characters.ExamplesGiven "abcabcbb", the answer is "abc", which the length is 3.Given "bbbbb", the answer is "b", with the length of 1.Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.分析首先,这种题肯定不能暴力来解决,否则肯定会超时。所以,考虑用一个哈希表(Map&l...阅读全文

Codeforces Round #345 (Div. 1) C. Table Compression

原题C. Table Compressiotime limit per tes4 secondmemory limit per tes256 megabyteinpustandard inpuoutpustandard outpuLittle Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.Petya decided to compress tables. He is give...阅读全文

动态规划解决最大子数组问题

问题Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4]the contiguous subarray [4,−1,2,1] has the largest sum = 6.问题来自于Leetcode:Maximum Subarra解决方式利用动态规划思想来解决最大子数组问题。之前的文章有写过有关动态规划的思路。如果你对动态规划不清楚可以通过这篇文章来简单了解下,里面有相应的视频还是不错的:拆分集合为两个和相等的子集合问题(动态规划)。该方法相对于分治法策略解决最大子数组问题来解决的时间复杂度中会有很大提升。时间复杂度O(n程序范例...阅读全文

拆分集合为两个和相等的子集合问题(动态规划)

题意问题描述:将1到N的连续整数组成的集合划分为两个子集合,且保证每个集合的数字和相等。例如,对于N=4,对应的集合{1,2,3,4},能被划分为{1,4}、{2,3}两个集合,使得1+4=2+3,且划分方案只有此一种。编程实现给定任一正整数N(1<=N<=39),输出其符合题意的划分方案数。样例输入1:样例输出1:1    (可划分为{1,2}、{3}样例输入2:样例输出2:1    (可划分为{1,3}、{2,4}样例输入3:样例输出3:4    (可划分为{1,6,7}、{2,3,4,5},或{1,2,4,7}、{3,5,6},或{1,3,4,6}、{2,5,7},或{1,2,5,6}、{3,4,7}思路根据动态规划思想,可以得到状态转移方程如下如果,对动态规划不理解建议看下这个视频:http://open.163.com/movie/2010/6/8/1/M6TCSIN...阅读全文