這題是標準的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()
這是一題標準的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
要計算最小合併成本，就需要用到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))
按照慣例，APCS的第二題就是考二維陣列的運用，特別是邊界的判別。解這題的時候如果你可以畫個圖，或是心中畫個圖的畫就會簡單許多。
現實的資料
m,n,k = [int(i) for i in input().split()]
s = []
for i in range(m):
s.append(input())
step = [int(i) for i in input().split()]
table = [[-1,0],[0,1],[1,1],[1,0],[0,-1],[-1,-1]]
x,y = 0,m-1
sets = set()
ans = ''
for i in step:
yy,xx = table[i]
if xx+x < 0 or xx+x >= n or yy+y < 0 or yy+y >= m:
ans += s[y][x]
sets.add(s[y][x])
continue
y,x = yy+y,xx+x
ans += s[y][x]
sets.add(s[y][x])
print(ans)
print(len(sets))乍看之下，本來覺得可以直接硬解，所以沒多想便用了很多清單來解題，沒想到過程中發現要記錄的資訊量很大，寫著寫著程式越來越複雜，所幸從頭開始，運用自訂結構，將每個節點所需要的欄位明確定義出來，這題就會簡單許多。
解題技巧運用到BFS再加上一些條件式判斷，依下圖為例：
class Node:
def __init__(self):
self.nexts = []#該節點是那些節點的輸入
self.val = -1
self.delay = 0
self.gate = None
self.ipt = []#那些節點是本節點的輸入
def t():
pp,q,r,m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
nodes = []
for i in range(pp+q+r):
nodes.append(Node())
for i in range(pp):
nodes[i].val = p[i]
for i in range(pp , pp+q):
nodes[i].gate = t[i-pp]
#print(nodes)
for i in range(m):
a,b = [int(i) for i in input().split()]
a -= 1
b -= 1
nodes[a].nexts.append(b)
p = [i for i in range(pp)]
'''1 為 AND、2 為 OR、3 為 XOR、4 為 NO'''
for i in p:
if nodes[i].val == -1:continue
for j in nodes[i].nexts:#i節點是j節點的輸入
nodes[j].ipt.append(i)#j節點的輸入有添加i節點
if nodes[j].gate == 4 and len(nodes[j].ipt) == 1:
nodes[j].val = int(not nodes[nodes[j].ipt[0]].val)#j節點的值，是j的輸入的值的相反
nodes[j].delay = nodes[nodes[j].ipt[0]].delay + 1
p.append(j)
elif nodes[j].gate != 4 and len(nodes[j].ipt) == 2:
p1,p2 = nodes[nodes[j].ipt[0]] , nodes[nodes[j].ipt[1]]
if nodes[j].gate == 1:
nodes[j].val = int(p1.val and p2.val)
if nodes[j].gate == 2:
nodes[j].val = int(p1.val or p2.val)
if nodes[j].gate == 3:
nodes[j].val = int(p1.val != p2.val)
nodes[j].delay = max(p1.delay , p2.delay) + 1
p.append(j)
mm = 0
for i in range(pp+q , pp+q+r):
mm = max(nodes[nodes[i].ipt[0]].delay , mm)
print(mm)
for i in range(pp+q , pp+q+r):
print(nodes[nodes[i].ipt[0]].val , end = ' ')
print()
t() 如果有問題，歡迎留言會email我。
