[leetcode] Climb Stairs | 小孩上楼梯

Posted by: lexigrey on: October 8, 2013

• In: classic | leetcode
• Leave a Comment

这个经典题居然submit了4遍才过，给33.8%的通过率拖后腿了。原因是忘记d[i]表示什么了就开始瞎写。就算做过的经典题，当场再想一想又有什么不好的？

d[i]表示到第i级台阶有几种走法。d[0]必须是1，这个是用i=1试出来的。最后返回d[n]不是d[n – 1]！

public int climbStairs(int n) {
  if (n == 0)
    return 0;
  int[] d = new int[n + 1];
  d[0] = 1;
  for (int i = 1; i <= n; i++) {
    d[i] += d[i - 1];
    if (i >= 2)
      d[i] += d[i - 2];
  }
  return d[n];
}

只用三个变量，不用array的做法（既然只看d[i – 1], d[i -2]往前看两个，那keep三个变量就够了。

public int climbStairs(int n) {
  if (n == 0)
    return 0;
  int prevPrev = 0;
  int prev = 1;
  for (int i = 1; i <= n; i++) {
    int curr = 0;
    curr += prev;
    if (i >= 2)
      curr += prevPrev;
    prevPrev = prev;
    prev = curr;
  }
  return prev;
}

Tags: 1WayDP