前言
动态规划类题型在遍历过程中,根据状态转移函数的不同,代码实现时遍历的方向也会有所差异。总的来说,一共可以总结为下图四种模式:
- 红色五角星表示当前要计算的状态值;
- 白底箭头代表哪些状态要提前算出来,才能推出红色五角星的状态值。
Python实现
# 上图第一行左图
row = 2
col = 2
for r in range(row-1, -1, -1):
for c in range(col):
print(r, c)
# 上图第一行右图
row = 2
col = 2
for r in range(row):
for c in range(col):
print(r, c)
# 上图第二行左图
row = 2
col = 2
for r in range(row-1, -1, -1):
for c in range(col-1, -1, -1):
print(r, c)
# 上图第二行右图
row = 2
col = 2
for r in range(row):
for c in range(col-1, -1, -1):
print(r, c)