SRM300 div1 medium

calc(n)をn以下のjumpyNumを求める関数とする
答えはcalc(high)-calc(low-1)
ーーーーーーーーーーーーcalc(n)の説明ーーーーーーーーーーーー
数字を文字列にして考える
n=123456789のとき
m=12345....なら、mはnにpos=4(0-indexed)までマッチしているということにする
DP[match][pos][digit]を数を左から右に考えていったとき、
場所posがdigit(0-9)なら何通りのjumpyNumが存在するかとしてDPする。
(matchはpos=0からpos=pos-1までがマッチしているかどうかを格納する)

#include <string>
#include <sstream>

using namespace std;

int ABS(int n)
{
	return (n<0)?-n:n;
}

class JumpyNum 
{
	public:

		int calc(int input)
		{
			stringstream ss;
			ss<<input;
			string num=ss.str();
			int n=num.size();
			int DP[2][15][10];

			for(int pos=n-1;0<=pos;pos--)
				for(int digit=0;digit<10;digit++)
					for(int match=0;match<2;match++)
						if(pos==n-1)
						{
							if(match)
								DP[match][pos][digit]=(digit<=num[pos]-'0')?1:0;
							else
								DP[match][pos][digit]=1;
						}
						else
						{
							if(match)
							{
								DP[match][pos][digit]=0;
								if(digit<num[pos]-'0')
									for(int nd=0;nd<10;nd++)
									{
										if(2<=ABS(digit-nd))
											DP[match][pos][digit]+=DP[0][pos+1][nd];
									}
								else if(digit==num[pos]-'0')
									for(int nd=0;nd<10;nd++)
									{
										if(2<=ABS(digit-nd))
											DP[match][pos][digit]+=DP[1][pos+1][nd];
									}
								else
									;
							}
							else
							{
								DP[match][pos][digit]=0;
								for(int nd=0;nd<10;nd++)
									if(2<=ABS(digit-nd))
										DP[match][pos][digit]+=DP[0][pos+1][nd];
							}
						}
			int ans=0;
			for(int len=1;len<=n;len++)
			{
				if(len==n)
				{
					for(int first=1;first<num[0]-'0';first++)
						ans+=DP[0][0][first];
					if(0<num[0]-'0')
						ans+=DP[1][0][num[0]-'0'];
				}
				else
				{
					for(int first=1;first<10;first++)
						ans+=DP[0][n-len][first];
				}
			}

			return ans;
		}

		int howMany(int low, int high) 
		{
			return calc(high)-calc(low-1);
		}
};