package dynamic;

/**
 * 题目:爬楼梯的最小代价
 *
 * @Author Gavin
 * @date 2022年01月09日 17:54
 */
public class solution_8 {
 /**
 * 解题思路:
 * C: 1 2 4 2
 * 每一次只能走一步或者两步
 * 首先状态方程为:
 * d(i)=min(d(i-1),d(i-2))+c(i)
 * d(0)=c(0)
 * d(1)=c(1)
 * <p>
 * 主要思路就是判断走一步和走两步对应下标值的和的大小,取最小的就是最小代价
 */
 //Time:O(n) Space:O(n)
 public int solution(int[] cost) {
 if (cost == null || cost.length == 0) return 0;
 if (cost.length == 1) return cost[0];
 int n = cost.length;
 int[] d = new int[n];
 d[0] = cost[0];
 d[1] = cost[1];
 for (int i = 2; i < n; i++) {
 d[i] = Math.min(d[i - 1], d[i - 2]) + cost[i];
 }
 return Math.min(d[n - 1], d[n - 2]);
 }

 //Time:O(n) Space:O(1)
 public int solution_2(int[] cost) {
 if (cost == null || cost.length == 0) return 0;
 if (cost.length == 1) return cost[0];
 int n = cost.length;
 int first = cost[0], second = cost[1];
 for (int i = 2; i < n; i++) {
 int cur = Math.min(first, second)+ cost[i];
 first = second;
 second = cur;
 }
 return Math.min(first, second);
 }
}