1.最長(zhǎng)增長(zhǎng)子序列
# 最長(zhǎng)遞增子序列
def dp_1(lst):
length = len(lst)
dp = [1 for i in range(length)]
ret = 1
for i in range(1, length):
for j in range(i):
if lst[j] < lst[i]:
dp[i] = max(dp[j] + 1, dp[i])
ret = max(ret, dp[i])
print(dp)
return ret
if __name__ == '__main__':
lst = list(map(lambda x: int(x), input('輸入一列數(shù)字:').split(' ')))
print(lst)
print(dp_1(lst))
2.數(shù)字三角形
# 數(shù)字金字塔
def main():
tower = []
floor = int(input('請(qǐng)輸入層數(shù):'))
for i in range(floor):
tower.append(list(map(lambda x: int(x), input('輸入第{}層的數(shù)字:'.format(i + 1)).split(' '))))
print(tower)
dp = [[0 for y in x] for x in tower]
print(dp)
for a in range(floor):
dp[floor - 1][a] = tower[floor - 1][a]
for b in range(floor - 2, -1, -1):
for c in range(0, b + 1):
dp[b][c] = max(dp[b + 1][c], dp[b + 1][c + 1]) + tower[b][c]
print(dp[0][0])
if __name__ == '__main__':
main()
3.斐波拉西數(shù)列
# 動(dòng)態(tài)規(guī)劃解決 fic
def main(len):
status_list = [0 for i in range(len)]
for i in range(len):
if i == 0:
status_list[i] = 1
elif i == 1:
status_list[i] = 1
else:
status_list[i] = status_list[i-1] + status_list[i-2]
print(status_list)
if __name__ == '__main__':
main(6)
4.求矩陣從左上到右下的最大路徑和
res = 0
matrix = [
[3, 4, 7],
[2, 9, 8],
[9, 5, 7],
[8, 9, 9],
[9, 3, 2]
]
def dp(x, y, status):
global res
if (x == y == 0):
res = status + matrix[x][y]
if (x - 1 >= 0 and y - 1 >= 0):
# 狀態(tài)轉(zhuǎn)移方程
dp(x, y - 1, status + matrix[x][y]) if matrix[x][y - 1] > matrix[x - 1][y] else dp(x - 1, y, status + matrix[x][y])
if (x == 0 and y > 0):
dp(x, y - 1, status + matrix[x][y])
if (x > 0 and y == 0):
dp(x - 1, y, status + matrix[x][y])
if __name__ == '__main__':
dp(len(matrix) - 1, len(matrix[0]) - 1, 0)
print(res)
解題思路：
- 1.找程序運(yùn)行邊界
- 2.大問(wèn)題分解成子問(wèn)題（遞歸或遞推）
- 3.狀態(tài)轉(zhuǎn)移方程
- 4.保留每個(gè)子問(wèn)題得到的狀態(tài)值status
