You are not using DP on this problem, but you can solve simply with using DP in O(n²) (because n ≤ 100). First, the problem is asking "minimum number of deletion", but it is same value to n — "maximum length of zigzag subsequence". Second, let dp[i][0] = "the maximum length of subsequence that ends in i and satisfying (the second element from the last) > (the last element), and dp[i][1] is almost same definition but (the second last) < (the last). And, the DP relation is: dp[i][0] = max(1, max_{j < i, a[j] > a[i]}{dp[j][1] + 1}), and dp[i][1] = max(1, max_{j < i, a[j] < a[i]}{dp[j][0] + 1}). Finally the answer is n - max(dp[n - 1][0], dp[n - 1][1]). My code is here (16-line in C++)
This is a main idea, but if the array has same values, you have to add dp[i][2] for equal and change DP relation a little.
EDIT: It's n ≤ 100 (real contest constraints) solution (It's O(n²) and of course if n ≤ 10000 you can solve it). I know you edited the blog and changed the constraints to n ≤ 100000.

just check left & right of the vector if somewhere condition will true.

#include <bits/stdc++.h>
using namespace std;

vector<int>v;

bool solve(int x, int y, int z)
{
    if(x >= v.size() || y >= v.size() || z >= v.size() || !x || !y || !z)
        return false;
    if( v[x] > v[y] && v[y] > v[z] )
        return true;
    if( v[x] < v[y] && v[y] < v[z] )
        return true;
    return false;
}

int main()
{
    int n, i, x, cnt=0;
    cin >> n;

    v.push_back(0);

    for(i=1; i<=n; i++)
    {
        cin >> x;
        v.push_back(x);
    }
    for(i=1; i<=v.size()-2; i++)
    {
        if( solve(i, i+1, i+2) && v.size() >= 3 )
        {
            cnt++;
            if( solve(i+1, i+2, i+3) )
                v.erase(v.begin()+i+2);
            else if( solve(i-1, i, i+1) )
                v.erase(v.begin()+i);
            else
                v.erase(v.begin()+i+1);
            i--;
        }
    }
    cout << cnt << endl;
    return 0;
}