DNI solution, followed by Jumping memoisation and Jumping bottom-up dp

dp.cpp

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int T, N, num[1000];
int dp[1000][2];



int main(){

	scanf("%d",&T);
	for(int t=1; t<=T; ++t){

		scanf("%d",&N);
		memset(dp,0,sizeof(dp));
		for(int i=0; i<N; ++i){
			scanf("%d",&num[i]);
		}

		dp[0][0] = num[0];
		for(int i=1; i<N; ++i){
			for(int s=0; s<2; ++s){
				dp[i][1] = max(dp[i-1][0],dp[i-1][1]);
				dp[i][0] = dp[i-1][1] + num[i];
			}
			//cout<<dp[i][0]<<' '<<dp[i][1]<<endl;
		}

		printf("Case #%d: %d\n",t, max(dp[N-1][0],dp[N-1][1]) );

	}

	return 0;
}

mem.cpp

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int T, N, num[1000];
int dp[1000][2];


int rec(int ind, bool sk){

	if(dp[ind][sk]!=0) return dp[ind][sk];

	if(ind==N) return 0;

	int res = rec(ind+1,1);
	if(sk){
		res = max( rec(ind+1,0) + num[ind], res);
	}

	dp[ind][sk]=res;
	return res;

}



int main(){

	scanf("%d",&T);
	for(int t=1; t<=T; ++t){

		scanf("%d",&N);
		memset(dp,0,sizeof(dp));
		for(int i=0; i<N; ++i){
			scanf("%d",&num[i]);
		}

		printf("Case #%d: %d\n",t,rec(0,1));

	}

	return 0;
}

sol.cpp

#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;


int T;
char dni[10], c;
char letter(int num) { return "TRWAGMYFPDXBNJZSQVHLCKE"[num%23]; }


int rec(int ind){

	if(ind==9){
		return letter(atoi(dni))==c;
	}

	if(dni[ind]!='?'){
		return rec( ind+1 );
	}

	int res=0;
	for(int i=0; i<10; ++i){
		dni[ind] = '0'+i;
		res += rec( ind+1 );
	}
	dni[ind]='?';
	return res;

}


int main(){

	scanf("%d",&T);
	
	while(T--){
		
		scanf("%s",&dni);
		c = dni[8];
		dni[8] = '\0';
		printf("%s%c %d\n",dni,c,rec(0));

	}

	return 0;

}