[LC]动态规划

满足动态规划的条件

1.状态可以转移

2.满足动态方程

3.目标可解

经典题目三角形的最小路径和，

[r,c ]为当前的列数，r为当前所处高度|行所处行

valueof(r,c) 为当前路径的值(最小值)

转移条件为当前行的最小值,转移次数是

[[0, 0]2,4,6,8,10....,2*(r-1)]

当r=0 min(r,0)=valueof(r,0)+valueof(r-1,0)

当c=r-1 min(r,c)=valueof(r,c)+valueof(r-1,c-1)

orther valueof(r,c)=min(valueof(r-1,c-1),valueof(r-1,c))+valueof(r,c)

程序实现的空间复杂度O(1)

时间复杂度为转移总次数

[0,0,4,6,...2*r-2]