作業2 遞精喔

第一個方法:

int climbStairs(int n) {

  if (n == 0 || n == 1)
    return n;

  int first = 1;
  int second = 2;

  for (int i = 3; i <= n; i++) {
    int next = first + second;
    first = second;
    second = next;
  }

  return second;
}

• 在第一個方法裡，我開了三個變數。
• 這三個變數是為了讓我的數值可以增加或者運算數值。

int first = 1;
int second = 2;
int next;

• 當變數n等於0或1時，他會return n自己的數值，也就是0或1。

if( n==0 || n==1 ) return n;

• 在for迴圈裡我做了運算來讓step可以一步加一步和把較大和較小的數值交換
• 有點類似Bubble Sort

for(int i = 3; i <= n; i++){
    next = first + second;
    first = second;
    second = next;
}

• 最後在return second的數值

return second;

第二個方法：

• 這個方法我使用了陣列和malloc()來解題。

int climbStairs(int n) {

  if (n == 1)
    return 1;
  if (n == 2)
    return 2;

  int *array = (int *)malloc((n) * sizeof(int));
  array[0] = 1;
  array[1] = 2;

  for (int i = 2; i < n; i++) {
    array[i] = array[i - 1] + array[i - 2];
  }

  return array[n - 1];
}

• 一開始先確定n的數值是1或2的時候就會回傳自己的數值。
• 有兩種方式去表達。

if(n == 1) return 1;
if(n == 2) return 2;

if(n == 1 || n == 2) return n;

• 在開array的變數的時候，我是用來malloc()的功能。
• malloc()會配置一個 int 需要的空間，並傳回該空間的位址。
• 可以使用指標 p 來儲存位址。

int *array = (int *)malloc((n) * sizeof(int));

• 在array裡開陣列來儲存數值。

array[0]=1;
array[1]=2;

• for迴圈裡做了一些運算來算出step的數值和交換。

for (int i = 2; i < n; i++) {
    array[i] = array[i - 1] + array[i - 2];
  }

• return array裡的陣列為什麼是n-1？
• 因為以上的運算，答案會比正確的數值大1，所以需要-1。

return array[n-1];

第三個方法：

• 這一個解題的方式有點像第二題，但是我使用了mod來改變運算方式。

int climbStairs(int n) {

  int *array = (int *)malloc(sizeof(int) * 2);
  array[0] = 1;
  array[1] = 1;

  for (int i = 2; i <= n; i++) {
    array[i % 2] = array[0] + array[1];
  }

  return array[n % 2];
}

• 在array的變數我也一樣使用了malloc()的功能。
• array的第一和第二陣列都等於1。

  int *array = (int *)malloc(sizeof(int) * 2);
  array[0] = 1;
  array[1] = 1;

• 由於array的第一陣列和第二陣列都是1，所以int i裡面需要等於2。
• 然後運算裡，array的陣列裡是n mod 2等於array[0]+array[1]。

for(int i = 2; i <= n; i++) {
    array[i % 2] = array[0] + array[1];
  }

• 最後return array[n%2]。

return array[n % 2];

謝謝！