1.最长增长子序列
# 最长递增子序列
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('输入一列数字:').split(' ')))
print(lst)
print(dp_1(lst))
2.数字三角形
# 数字金字塔
def main():
tower = []
floor = int(input('请输入层数:'))
for i in range(floor):
tower.append(list(map(lambda x: int(x), input('输入第{}层的数字:'.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.斐波拉西数列
# 动态规划解决 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):
# 状态转移方程
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.找程序运行边界
- 2.大问题分解成子问题（递归或递推）
- 3.状态转移方程
- 4.保留每个子问题得到的状态值status
