# 演算法題 - A Frog 1 - Atcoder - by PeterWang
## 題目資訊 Atcoder DP contest
###### tags: `Atcoder` `DP`

## 題目敘述

有 *N* 個石頭，給個石頭有不同高度，一隻青蛙從第一顆石頭開始，每次可以選擇跳一格或兩格而每從第 *i* 個跳到第 *j* 個的花費為兩石頭高度相減的絕對值，最後回傳總花費最小值為何。

### 輸入：
先輸入總共有 *N* 個石頭，再依序輸入第 *i* 個石頭的高度

### 輸出：
到達地 *N* 個石頭前最小的花費

## 解題思路
每到一塊石頭，就去比較前兩塊跳過來的花費，並選擇最小值加總。

## 程式碼

#include <iostream>
#include <cmath>
using namespace std;
int main() {
  int n;
  cin>>n;
  int a[n];
  int dp[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  dp[0]=0;
  dp[1]=abs(a[1]-a[0]);
  for(int i=2;i<n;i++){
    dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
  }
  cout<<dp[n-1]<<endl;
  return 0;
}

## 資料來源
[Atcoder](https://atcoder.jp/)
[題目敘述](https://atcoder.jp/contests/dp/tasks/dp_a)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 10:00 AM]