プロジェクトオイラー問113 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20113
Problem 113 「非はずみ数」 †
10＾100までに存在する増加数か減少数である数の個数をこたえる問題。

解法
何も考えない動的計画法で自然に片が付きます
解説する内容がありません。

#include<stdio.h>
#include<string.h>
#include<iostream> 

const int LIMIT=101;
__int64 dpUp[LIMIT][10],dpDown[LIMIT][10];
int main()
{ 
memset(dpUp,0,sizeof(dpUp));
 	memset(dpDown,0,sizeof(dpDown));
	__int64 all=0;
	for(int i=0;i<10;i++){
		dpUp[0][i]=dpDown[0][i]=1;
	}
	for(int i=1;i<LIMIT;i++){
		__int64 upSum=0,downSum=0;
		for(int j=0;j<=9;j++){
 			upSum+=dpUp[i-1][j];
			dpUp[i][j]=upSum;
		}	
		for(int j=9;j>=0;j--){
			downSum+=dpDown[i-1][j];
			dpDown[i][j]=downSum;
		}
 		dpDown[i][0]=0;
		all+=downSum+upSum-10;
		std::cout<<"桁="<<i<<" ans="<<all-1<<"\n";
	}
}