字符串

1 最长无重复字符子串

class DistinctSubstring:
    def longestSubstring(self, A, n):
        # write code here
        dic = {}
        pre = -1
        length = 0
        maxlen = 0
        
        for i in range(n):
            if A[i] not in dic:
                length = i - pre
                dic[A[i]] = i
                maxlen = max(length, maxlen)
            else:
                if dic[A[i]] > pre:
                    length = i - dic[A[i]]
                    pre = dic[A[i]]
                else:
                    length = i - pre
                maxlen = max(length, maxlen)
                dic[A[i]] = i
        return maxlen

2 最长上升子序列（动态规划）

class LongestIncreasingSubsequence:
    def getLIS(self, A, n):
        # write code here
        dp = [0 for i in range(n)]
        dp[0] = 1
        for i in range(1,n):
            tmp = 0
            for j in range(i):
                if A[j] < A[i] and tmp < dp[j]:
                    tmp = dp[j]
                dp[i] = tmp+1
        return max(dp)

3 最长公共子序列的长度（动态规划）

class LCS:
    def findLCS(self, A, n, B, m):
        # write code here
        if A == None or B == None:
            return 0
        dp = [[0]*n for i in range(m)]
        
        if A[0] == B[0]:
            dp[0][0] = 1
        else:
            dp[0][0] = 0

            
        for i in range(1,n):
            if B[0] == A[i]:
                dp[0][i] == 1
            else:
                dp[0][i] == dp[0][i-1]
        for i in range(1,m):
            if A[0] == B[i]:
                dp[i][0] == 1
            else:
                dp[i][0] == dp[i-1][0]

                
        for i in range(1,m):
            for j in range(1,n):
                if A[j] == B[i]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

4 对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串

class Parenthesis:
    def chkParenthesis(self, A, n):
        num = 0
        for i in A:
            if i == '(':
                num += 1
            if i == ')':
                num -= 1
            if num < 0:
                return False
        if num == 0:
            return True
        return False

5 找零钱

有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以
使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。

给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。

测试样例：
[1,2,4],3,3
返回：2 

class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        matrix = [[0 for i in range(aim+1)] for j in range(n)]
        for i in range(aim+1):
            if i % penny[0] == 0:
                matrix[0][i] = 1
            else:
                matrix[0][i] = 0
        for i in range(n):
            matrix[i][0] = 1
        for i in range(1,n):
            for j in range(1,aim+1):
                if j - penny[i] < 0:
                    matrix[i][j] = matrix[i-1][j]
                else:
                    matrix[i][j] = matrix[i-1][j] + matrix[i][j-penny[i]]
        return matrix[-1][-1]

6 01背包

一个背包有一定的承重cap，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录
在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的
总价值最大。

给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值。

测试样例：
[1,2,3],[1,2,3],3,6
返回：6

class Backpack:
    def maxValue(self, w, v, n, cap):
        # write code here
        matrix = [[0]*(cap+1) for i in range(n)]
        for i in range(cap+1):
            if w[0] <= i:
                matrix[0][i] = v[0]
            else:
                matrix[0][i] = 0
        for j in range(n):
            matrix[j][0] = 0
        
        for i in range(1,n):
            for j in range(1,cap+1):
                if w[i] > j:
                    matrix[i][j] = matrix[i-1][j]
                else:
                    matrix[i][j] = max(matrix[i-1][j], matrix[i-1][j-w[i]] + v[i])
        return matrix[-1][-1]

7 最优编辑

对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种
操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。

给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串
长度均小于等于300，且三种代价值均小于等于100。

测试样例：
"abc",3,"adc",3,5,3,100
返回：8

class MinCost:
    def findMinCost(self, A, n, B, m, c0, c1, c2):
        # write code here
        dp = [[0] * (n+1) for _ in range(m+1)]
        #dp = [[0 for j in range(m+1)] for i in range(n+1)]
        #dp[0][0] = 0
        for i in range(1,n+1):
            dp[0][i] = c1 * i
        for j in range(1,m+1):
            dp[j][0] = c0 * j
            
        for i in range(1,m+1):
            for j in range(1,n+1):
                if A[j-1] == B[i-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j]+c0, dp[i][j-1]+c1, dp[i-1][j-1]+c2)
        return dp[-1][-1]