Link

https://leetcode.com/problems/number-of-longest-increasing-subsequence/

My code:

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if len(nums) ==0: return 0
        if len(nums) ==1: return 1
        #The list contains the maximum length end up with ith element in the nums
        ResultList = [[1,1]]
        #The dictionary provides the number of list given in the list
        for i in range(1,len(nums)):
            IndexList = []
            Length =1
            Num = 0
            for j in range(i):
                if nums[i]>nums[j]:
                    Length = max(Length,ResultList[j][0]+1)
                    IndexList.append(j)
            if Length != 1:
                for k in IndexList:
                    if ResultList[k][0] == Length -1:
                        Num += ResultList[k][1]
            if Num == 0:
                Num = 1
            ResultList.append([Length,Num])
        LengthList = [ResultList[i][0] for i in range(len(ResultList))]
        MaxLength = max(LengthList)
        Sum  = 0
        for s in range(len(ResultList)):
            if ResultList[s][0] == MaxLength:
                Sum += ResultList[s][1]
        return Sum

Explanation: There are two main problems in this question:1. How to determine the maximum length 2. How to count all the subsequence with maximum length. Here is the way I solve it. I construct a list L such that L[i] is a list that contains two elements. First element is the maximum length that ends up with element nums[i] and second element is the number of such subsequences. The recursion relation is as follows: for i+1 th element, we first check if it is larger than the chosen previous element. If so, then we know that the length of new List would be the maximum length of subsequence that ends up with chosen previous element plus one. Iterate through the beginning we may get the maximum length that ends up with i+1 th element. Second is to determine the number of the elements that ends up with i+1 th element and equals to the maximum length. So I do the iteration again to find total number. Notice that I initialise the length as 1 and Num as 0 because there is a situation that the i+1 th element might be smaller than all previous elements. In this situation , the maximum length would be one as itself. and the number would be 1 as just itself. Hence we iterate throught the nums list. Then we first find out the maximum length. Then we sum all the numbers that gives the maximum length. Then we return the result.

Link

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

My Code:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if k>= len(cardPoints):
            return sum(cardPoints)
        else:
            RestLength = len(cardPoints) - k
            TotalSum = sum(cardPoints)
            PartSum = sum(cardPoints[0:RestLength])
            Min =PartSum
            for new in range(RestLength,len(cardPoints)):
                old = new -RestLength
                PartSum= PartSum - cardPoints[old]+cardPoints[new]
                Min = min(Min,PartSum)
            return TotalSum - Min

Explanation: The idea is clear , no matter which side you choose, the list left must be continuous and the length is total length – k. Then we just need to write an iteration to calculate minimum of the list. Notice that if we use sum function here, it will exceed time limit as sum function also originates from the iteration.

Link:

https://leetcode.com/problems/triangle/

My Code:

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        TriangleLength = len(triangle)
        MinTri = [triangle[0]]
        for i in range(1,TriangleLength):
            CheckLen = len(triangle[i])
            MinList = []
            for j in range(CheckLen):
                if j == 0:
                    MinList.append(triangle[i][0]+MinTri[i-1][0])
                elif j == (CheckLen -1):
                    MinList.append(triangle[i][CheckLen-1]+MinTri[i-1][CheckLen-2])
                else:
                    Min = min(MinTri[i-1][j],MinTri[i-1][j-1])+ triangle[i][j]
                    MinList.append(Min)
            MinTri.append(MinList)
        return min(MinTri[TriangleLength-1])

Explanation: The idea is clear, for each element in the triangle, we search for the minimum path number among all the available previous element, then take the minimum to get the minimum path sum at this point.

Link

https://leetcode.com/problems/longest-increasing-subsequence/

My Code:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) ==0:
            return 0
        else:
            ResultList = [1]
            for i in range(1,len(nums)):
                Max = 1
                for j in range(i):
                    if nums[i]>nums[j]:
                        Max = max(Max,ResultList[j]+1)
                ResultList.append(Max)
            return max(ResultList)

Explanation: we set the ResultList as the longest subsequence up to element k in the sequence. Then for next element, we just need to check if it is larger than the previous elements. If it is larger, then we just append the element to the previous subsequence, corresponding to the code ResultList[j] +1, then we take the Max among all the possible choices. if it is smaller then all previous elements, then we set the number as 1 in the list.

Then we just need to return the maximum among all the result in the list.

Link:

My Code:

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        LargestSum = sum(nums)
        SmallestSum = -LargestSum
        if LargestSum<S or SmallestSum>S:
            return 0
        else:
            ResultMat = []
            for l in range(len(nums)):
                List = [0]*(LargestSum*2+1)
                ResultMat.append(List)
            ResultMat[0][nums[0]] = ResultMat[0][nums[0]]+1
            ResultMat[0][-nums[0]] = ResultMat[0][-nums[0]]+1
            for i in range(1,len(nums)):
                for j in range(-LargestSum,LargestSum+1,1):
                    Index1 = j-nums[i]
                    Index2 = j+nums[i]
                    if Index1 <-LargestSum:
                        Value1 =0
                    else:
                        Value1 = ResultMat[i-1][Index1]
                    if Index2> LargestSum:
                        Value2 = 0
                    else:
                        Value2 = ResultMat[i-1][Index2]
                    Value = Value1+Value2
                    ResultMat[i][j] = Value
            return ResultMat[len(nums)-1][S]

Explanation: I use a two dimension matrix to store the data. The row is the ith element of the original list, the column is the Sum j and the value stored in the matrix[i][j] is the total number that can achieve value j at the ith index. Then to for i+1 Index, the only way to achieve the sum j is that we have achieved j+ nums[i+1] or j-nums[i+1] at the index i. Hence we just sum these two values together to get the total number that can achieve j at i+1.

Link:

https://leetcode.com/problems/perfect-squares/

My Code:

class Solution:
    def numSquares(self, n: int) -> int:
        if n ==1:
            return 1
        else:
            NumList = [0]
            for Number in range(1,n+1):
                Min = 2**31
                SquareNum = math.floor(math.sqrt(Number))
                for j in range(1,(SquareNum+1)):
                    Min = min(Min,NumList[Number-j**2])
                NumList.append((Min+1))
            return NumList[n]

Explanation

It is clear that we for number a , we may check the number squares the a-k is made of and then take the minimum among them. A typical dynamic programming problem.