今日题目
爬楼梯
三角形最小路径和
1.爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?...,而不需要新增一个temp变量。...每一步只能移动到下一行中相邻的结点上。...1,-1,-3]
]
求和:
[
[-1+min(1,0)=-1],
[2+min(1,-1)=1,3+min(-1,-3)=0],
[1,-1,-3]
]
由此图可知,自底向上计算...一开始最后一行所有数据不变,我们就想要最后一行的原数据存储到我们的dp数组中,后面我们就是不断修改对应(i,j)的位置,因为是从底向上的,也就是每一行的每一列数据它只修改一次,所以直接使用原数组即可,空间复杂度达到了