Go: package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

const (
	initialBufSize = 10000000
	maxBufSize     = 100000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	return sc
}

func main() {
	sc = initScanner(os.Stdin)
	resolve()
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	a, _ := strconv.Atoi(sc.Text())
	return int(a)
}
func nextString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextIntSlice(sc *bufio.Scanner, n int) (a []int) {
	a = make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt(sc)
	}
	return a
}

var dp [][]int

func initDP(n int) {
	dp = make([][]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+1)
		for j := 0; j < len(dp[0]); j++ {
			dp[i][j] = -1
		}
	}
}

func resolve() {
	ans := []int{}
	for true {
		n := nextInt(sc)
		if n == 0 {
			break
		}
		as := nextIntSlice(sc, n)
		initDP(n)
		_rec(as, n, 0, n)
		ans = append(ans, dp[0][n])
	}
	for _, v := range ans {
		fmt.Println(v)
	}
	return
}

func _rec(as []int, n, l, r int) int {
	if dp[l][r] > -1 {
		return dp[l][r]
	}
	if r-l == 1 { // prevent to hit daruma
		dp[l][r] = 0
		return dp[l][r]
	}
	if r-l == 2 {
		if abs(as[l]-as[r-1]) <= 1 {
			dp[l][r] = 2
		} else {
			dp[l][r] = 0
		}
		return dp[l][r]
	}
	if abs(as[l]-as[r-1]) <= 1 {
		v := _rec(as, n, l+1, r-1)
		// if we can remove internal blocks
		if (r - 1 - (l + 1)) == v {
			dp[l][r] = v + 2
			return dp[l][r]
		} else {
			dp[l][r] = v
		}
	}
	for i := l + 1; i < r; i++ {
		v := _rec(as, n, l, i) + _rec(as, n, i, r)
		if dp[l][r] < v {
			dp[l][r] = v
		}
	}
	return dp[l][r]
}

func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}

Python: # AOJ 1611 ダルマ落とし
# 貰うdp

import sys


def main():
    while True:
        N = int(input())
        if N == 0:
            break
        w = list(map(int, sys.stdin.readline().strip().split()))

        # dp 初期化 -------------------------------------------------
        dp = [[0] * N for _ in range(N)]

        for i in range(N - 1):
            if abs(w[i] - w[i + 1]) <= 1:
                dp[i][i + 1] = 2

        # dp 更新 ------------------------------------------------------
        for l in range(2, N):
            for i in range(N - l):
                j = i + l

                if l % 2 == 1:
                    if dp[i + 1][j - 1] == l - 1 and (abs(w[i] - w[j]) <= 1):
                        dp[i][j] = l + 1
                        continue

                for k in range(i, j):
                    if dp[i][j] < dp[i][k] + dp[k + 1][j]:
                        dp[i][j] = dp[i][k] + dp[k + 1][j]
                        if dp[i][j] == l:
                            break

        # for i in range(len(dp)):
        #     print(dp[i])

        print(dp[0][-1])


if __name__ == '__main__':
    main()

Python: import sys
sys.setrecursionlimit(10000)

def f(daruma):
	global flag, min
	if (flag):
		return

	length = len(daruma)
	if (daruma == 0 or daruma == 1):
		print(n - length)
		flag = true
		return

	for i in range(length-1):
		diff = abs(daruma[i] - daruma[i+1])
		if (diff < 2):
			kari_daruma = daruma[:i] + daruma[i+2:]
			f(kari_daruma)
	else:
		min = (min if min <= length else length)
		return

while 1:
	count = 0
	flag = False
	
	n = int(input())
	if (n == 0):
		break
	min = n
	daruma = list(map(int, input().split()))
	f(daruma)
	print(n - min)

Python: n = int(input())
while True:
    l1 = list(map(int,input().split()))
    c = [[False] * n for i in range(n)]
    d = [0] * (n + 1)
    for i in range(n - 1):
        if abs(l1[i + 1] - l1[i]) <= 1:
            c[i][i + 1] = True
            
    for i in range(3, n, 2):
        for j in range(n - i):
            for k in range(j + 1, j + i):
                if c[j][j + i] == False and c[j][k] and c[k + 1][j + i]:
                    c[j][j + i] = True
                    break
            if c[j][j + i] == False and abs(l1[j] - l1[j + i]) <= 1 and c[j + 1][j + i - 1]:
                c[j][j + i] = True
                
    for i in range(n):
        for j in range(i):
            if c[j][i]:
                d[i] = max(d[i], d[j - 1] + i - j + 1)
        d[i] = max(d[i], d[i - 1])
        
    print(d[n - 1])
    
    n = int(input())
    if n == 0:
        break

Python: import sys
sys.setrecursionlimit(10000)
def f(daruma):
	global flag, min
	if (flag):
		return

	length = len(daruma)
	if (daruma == 0 or daruma == 1):
		print(n - length)
		flag = true
		return

	for i in range(length-1):
		diff = abs(daruma[i] - daruma[i+1])
		if (diff < 2):
			kari_daruma = daruma[:i] + daruma[i+2:]
			f(kari_daruma)
	else:
		min = (min if min <= length else length)
		return

while 1:
	count = 0
	flag = False
	
	n = int(input())
	if (n == 0):
		break
	min = n
	daruma = list(map(int, input().split()))
	f(daruma)
	print(n - min)

Python: #!usr/bin/env python3
import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 8)
def solve():
    n = int(input())
    while n != 0:
        w = tuple(map(int, input().split()))
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if (j - i + 1) % 2 == 0:
                    if dp[i + 1][j - 1] == j - i - 1 and abs(w[i] - w[j]) <= 1:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        p = tuple(dp[i][k] + dp[k + 1][j] for k in range(i, j + 1))
                        dp[i][j] = max(p)
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
        print(dp[0][n - 1])
        n = int(input())


if __name__ == "__main__":
    solve()

Python: 
while True:
    n=int(input())
    if n== 0:
        break
    
    A = list(map(int, input().split()))
    c = [[0]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0
        
    for i in range(1, n):
        if i%2==0:
            continue
        for j in range(n-i):
            if i==1 and abs(A[j] - A[j+i])<=1:
                    c[j][j+i] = 1 
            else:
                for k in range(j+1, j+i-1):
                    #print(f'j:{j}, i:{i}, k:{k}, c[j][k]{c[j][k]} and c[k+1][j+i]{c[k+1][j+i]}')
                    if c[j][k] and c[k+1][j+i]:
                        c[j][j+i] = 1
                        break
                if c[j+1][j+i-1] and abs(A[j] - A[j+i])<=1:
                    c[j][j+i] = 1
    
    dp = [[0]*n for _ in range(n)]
    
    for i in range(1):
        for j in range(i, n):
            if c[i][j]:
                dp[i][j] = j-i+1
            else:
                for k in range(i, j):
                    if c[k+1][j]:
                        dp[i][j] = max(dp[i][j], dp[i][k] + j-k)
                if j>i:
                    dp[i][j] = max(dp[i][j], dp[i][j-1])
    
    print(dp[0][n-1])

Python: while True:
    N = int(input())
    if not N:
        break
    W = [int(x) for x in input().split()]
    dp = [[0] * N for _ in range(N)]
    for w in range(2, N + 1):
        for left in range(N - w + 1):
            # [left, right]
            right = left + w - 1
            for mid in range(left + 1, right):
                dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid + 1][right])
            if right - left - 1 == dp[left + 1][right - 1] and abs(W[left] - W[right]) <= 1:
                dp[left][right] = right - left + 1
    print(dp[0][N-1])