DP入门 leetcode题目为例

解决dp问题，关键分为两步，第一步摆出初始状态，第二步列出状态转移方程。

leetcode 70.爬楼梯

初始状态，在第一层楼梯时，明显只有一种方法 F[1] = 1；在第二层楼梯时，有两种方法，F[2] = 2。

状态转移方程，可以看到，在第三层楼梯时，可以由第一层走两个，或者是在第二层走一个台阶到达，那么到达第三层楼梯的方法数目就是第一层的加上第二层的数目

以此类推，到达第i层楼梯的方法数就等于第i-1层的加上第i-2层的方法数

则状态转移方程为 F[i] = F[i-1] + F[i-2]

leetcode 746.使用最小花费爬楼梯

注意这道题和上一题在初始状态上就不一样，可以选择从下标为0或者下标为1的台阶开始爬楼梯，那就意味着站在下标为0或者1的台阶上的花费是0。初始状态为 F[0] = F[1] = 0

状态转移方程：在第i个台阶上，可以由第i-2个台阶上两步，此时花费是到达第i-2的台阶的最小花费加上其本身的花费；或者由第i-1个台阶上一步，此时花费是到达第i-1个台阶的最小花费加上其本身的花费。为了使花费最小，应该选择这两种状况的最小者。

则状态转移方程为 F[i] = min(F[i-1]+cost[i-1] , F[i-2]+cost[i-2] )

值得注意的是到达第i个台阶是不花费其本身第i的台阶的消耗值的