h206. 強者就是要戰，但......什麼才是強者呢？

         這題是很好的遞迴問題，每次遞迴的時候都要帶入此次遞迴的左右邊界、及這次是要取區間最大還是取區間最小的flag。

        完整程式如下：

def t(l , r , isBig):
    if l == r-1:
        return d[l]
    m = (l+r)//2
    if isBig: 
        g = max(t(l,m,0) , t(m,r,0))
    else:
        g = min(t(l,m,1) , t(m,r,1))
    return g
        
n = int(input())
d = [int(i) for i in input().split()]

print(t(0,n,1))

k740. 楊輝三角形

        這題是標準的DP問題，扣除每一行的頭跟尾(都是1)，每一行的資料都是由上一行的正上方與左上方提供。

        以下附上完整程式碼：

n = int(input())
d = [[1 for i in range(21)] for j in range(21)]

for i in range(1,n+1):
    for j in range(i):
        if j != 0 and j != i-1:
            d[i][j] = d[i-1][j] + d[i-1][j-1]
        print(d[i][j] , end = ' ')
    print()

m283. 螞蟻的擴散

         這是一題標準的DP題目，假設以dp[x][y]做為起點開始走，那麼從dp[x][y]走一步後，dp[x-1][y]跟dp[x][y-1],dp[x-1][y-1]這三個位置個會增加dp[x][y]/3的機率被走到，以此類推直到X或是Y軸為0，最後計算起點跟終點的比值即可。

        下列附上程式：

import math

def cal(x, y):
    # 初始化dp陣列
    dp = [[0] * 11 for _ in range(11)]
    
    # 設定起點的機率為1
    dp[x][y] = 1*3**(x+y)
    
    # 遞迴計算dp
    for i in range(x, 0, -1):
        for j in range(y, 0, -1):
            dp[i-1][j] += dp[i][j] / 3
            dp[i][j-1] += dp[i][j] / 3
            dp[i-1][j-1] += dp[i][j] / 3
    
    ans = int(dp[x][y] - dp[0][0])
    cc = math.gcd(int(ans), int(dp[x][y]))
    dp[x][y] //= cc
    ans //= cc
    print(str(ans) + "/" + str(dp[x][y]))
    # 將分數化簡
    '''common_factor = math.gcd(int(result), 81)
    result /= common_factor'''

try:
    while True:
        x,y = [int(i) for i in input().split()]
        cal(x,y)
except:
    pass

APCS 2024.01 m934. 4. 合併成本

        要計算最小合併成本，就需要用到DP，DP的精髓就是分而治之，假設今天只有3個資料要合併，-1,3,-5，那麼情形不外乎是(-1,(3,-5) ) 或是 ((-1, 3),-5)，從兩個之中找最小成本。如果這時候再增加一個資料如-1,3,-5,6那麼情形就是((-1,3,-5),6)或是((-1,3),(-5,6))或是(-1,(3,-5,6))之中找最小成本，我們可以發現，只要每次切割區間的左右邊界，直到找到1.左右邊界相同，代表沒有合併成本，2.左右邊界差一，那就是相鄰兩個合併，可以直接運算，3.這個左右邊界夾出來的最小成本已經算過，直接回傳資料。

        以下附上完整程式碼：

def check(left , right):
    if dp[left][right] != 9999999:
        return dp[left][right]
    if left == right: return 0
    elif left == right-1:
        return abs(d[left] - d[right])
    mm = 9999999
    for i in range(left , right):
        l,r = check(left , i) , check(i+1 , right)
        dp[left][right] = min(dp[left][right],abs((table[i+1] - table[left]) - (table[right+1] - table[i+1]))  + l+r)
        mm = min(mm,dp[left][right])
    return mm
        

n = int(input())
d = [int(i) for i in input().split()]
dp = [[9999999 for i in range(n)] for j in range(n)]
table = [0]
for i in d:
    table.append(table[-1] + i)

print(check(0,n-1))