Question 1: 509. Fibonacci number

Fibonacci numbers are usually represented by F(n), and the sequence formed is called Fibonacci sequence. The sequence starts with 0 and 1, and each subsequent number is the sum of the first two numbers. That is:

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2), where n > 1
Here you are n, please calculate F(n).

class Solution:
    def fib(self, n: int) -> int:
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            return self.fib(n-1) + self.fib(n-2)

result:

Question 2: N th teponacci number

The teponacci sequence ， Tn ， is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 under the condition of N > = 0 +

Here is the integer ， n. please return the value of the nth teponacci number ， Tn.

class Solution:
    def tribonacci(self, n: int) -> int:
        if n==0:
            return 0
        if n<=2:
            return 1
        p = 0
        q = r = 1
        for i in range(3,n+1):
            s = p + q + r
            p,q,r = q,r,s
        return s

result:

Question 3: 70. Climb stairs

Suppose you are climbing stairs. You need n steps to reach the roof.

You can climb one or two steps at a time. How many different ways can you climb to the roof?

class Solution:
    def climbStairs(self, n: int) -> int:
        if n==1:
            return 1
        elif n==2:
            return 2
        p = 1
        q = 2
        for i in range(3,n+1):
            s = p+q
            p,q = q,s
        return s

result:

 

Question 4: 746. Use the minimum cost to climb stairs

Give you an integer array cost, where cost[i] is the cost of climbing up the ith step of the stairs. Once you pay this fee, you can choose to climb up one or two steps.

You can choose to climb the stairs from the steps with subscript 0 or subscript 1.

Please calculate and return the minimum cost to reach the top of the stairs.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[n]

result:

Question 5: 121. The best time to buy and sell stocks

Given an array of prices, its ＾ i-th element ＾ prices[i] represents the price of a given stock on day I.

You can only choose to buy this stock one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from this transaction. If you can't make any profit, return 0.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [0]
        if not bool(prices):
            return 0
        else:
            temp = prices[0]
            for i in range(1,len(prices)):
                temp = min(temp,prices[i])
                dp.append(max(dp[i-1],prices[i] - temp))
            return max(dp)

Results:

Question 6: Sword finger Offer II 095 Longest common subsequence

Given two strings, {text1 and} text2, returns the length of the longest common subsequence of the two strings. If there is no common subsequence, 0 is returned.

The {subsequence of a string refers to such a new string: it is a new string composed of the original string after deleting some characters (or not deleting any characters) without changing the relative order of characters.

For example, "ace" is a subsequence of "abcde", but "aec" is not a subsequence of "abcde".
The common subsequence of two strings is the subsequence shared by the two strings.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[m][n]

result:

Question 7: Yang Hui triangle

 

n = int(input(''))
arr = []
for i in range(n):
    arr.append([])
    for j in range(i+1):
        if j == 0 or i == j:
            arr[i].append(1)
        else:
            arr[i].append(arr[i-1][j-1] + arr[i-1][j])
    print(" ".join(str(a) for a in arr[i]))

result:

Question 9: node selection

code:

def dfs(node,pre):
    global value,table
    for i in table.get(node):
        if i !=pre:
            dfs(i,node)
            value[node][0]+=max(value[i][0],value[i][1])
            value[node][1]+=value[i][0]

def main():
    global value, table
    n = int(input())
    value = list(map(int, input().split()))
    value = list(map(lambda x:[0,x],value))
    value.insert(0,0)
    table = {}
    for i in range(n):
        table.update({i + 1: []})
    for i in range(n - 1):
        father, child = list(map(int, input().split()))
        table.get(father).append(child)
        table.get(child).append(father)
    print(table)
    dfs(1,0)
    print(max(value[1][0],value[1][1]))

if __name__=='__main__':
    main()

Question 10: Fall resistance index:

Question 11: K good number