DP:

DP[len][k][i][j] 再第len位，第一个数len位为i，第二个数len位为j，和的第len位为k

每一位可以从后面一位转移过来，可以进位也可以不进位

A Famous Equation

7+1?=1?
?1+?1=22

Case 1: 3
Case 2: 1

Hint
There are three solutions for the first case:
7+10=17, 7+11=18, 7+12=19
There is only one solution for the second case:
11+11=22
Note that 01+21=22 is not a valid solution because extra leading zeros are not allowed.
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

typedef long long int LL;

char cpp[200];
int a[200],len1,b[200],len2,c[200],len3;
LL dp[20][20][20][20];

int main()
{
    int cas=1;
    while(cin>>cpp)
    {
        len1=len2=len3=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        int n=strlen(cpp);
        int i; stack<char> stk;
        for(i=0;i<n;i++)
        {
            if(cpp[i]=='+')
            {
                while(!stk.empty())
                {
                    char c=stk.top(); stk.pop();
                    if(c!='?') a[len1++]=c-'0';
                    else a[len1++]=-1;
                }
                i++;
                break;
            }
            stk.push(cpp[i]);
        }
        for(;i<n;i++)
        {
            if(cpp[i]=='=')
            {
                while(!stk.empty())
                {
                    char c=stk.top(); stk.pop();
                    if(c!='?') b[len2++]=c-'0';
                    else b[len2++]=-1;
                }
                i++;
                break;
            }
            stk.push(cpp[i]);
        }
        for(;i<n;i++) stk.push(cpp[i]);
        while(!stk.empty())
        {
            char cc=stk.top(); stk.pop();
            if(cc!='?') c[len3++]=cc-'0';
            else c[len3++]=-1;
        }

        for(int i=len1-1;i>0;i--) if(a[i]==0) len1--; else break;
        for(int i=len2-1;i>0;i--) if(b[i]==0) len2--; else break;
        for(int i=len3-1;i>0;i--) if(c[i]==0) len3--; else break;

        memset(dp,0,sizeof(dp));

        ///len==0
        for(int i=0;i<=9;i++)
        {
            if(a[0]==-1||a[0]==i)
            for(int j=0;j<=9;j++)
            {
                if(b[0]==-1||b[0]==j)
                for(int k=0;k<=9;k++)
                if(c[0]==-1||c[0]==k)
                {
                    if(k==(i+j)%10)
                        dp[0][k][i][j]=1;
                }
            }
        }
        ///len=1...
        for(int len=1;len<len3;len++)
        {
            for(int i=0;i<=9;i++)
            {
                if(len==len1-1&&i==0) continue;
                if(len>=len1&&i!=0) continue;
                if(a[len]==-1||a[len]==i)
                for(int j=0;j<=9;j++)
                {
                    if(len==len2-1&&j==0) continue;
                    if(len>=len2&&j!=0) continue;
                    if(b[len]==-1||b[len]==j)
                    for(int k=0;k<=9;k++)
                    {
                        if(len==len3-1&&k==0) continue;
                        if(((i+j)%10!=k)&&((i+j+1)%10!=k))
                                continue;
                        if(c[len]==-1||c[len]==k)
                        {
                            ///没有进位
                            if((i+j)%10==k)
                            {
                                for(int ii=0;ii<=9;ii++)
                                    for(int jj=0;jj<=9;jj++)
                                        for(int kk=0;kk<=9;kk++)
                                        {
                                            if((ii+jj==kk)||(ii+jj+1==kk))
                                                dp[len][k][i][j]+=dp[len-1][kk][ii][jj];
                                        }
                            }
                            ///有进位
                            if((i+j+1)%10==k)
                            {
                                 for(int ii=0;ii<=9;ii++)
                                    for(int jj=0;jj<=9;jj++)
                                        for(int kk=0;kk<=9;kk++)
                                        {
                                            if(((ii+jj>=10)&&(ii+jj)%10==kk)||((ii+jj+1>=10)&&(ii+jj+1)%10==kk))
                                                dp[len][k][i][j]+=dp[len-1][kk][ii][jj];
                                        }
                            }
                        }
                    }
                }
            }
        }
        LL ans=0;
        int mx=max(len1,max(len2,len3));
        for(int i=0;i<=9;i++)
            for(int j=0;j<=9;j++)
                for(int k=0;k<=9;k++)
                    if((i+j==k)||(i+j+1==k))
                    {
                        if(mx==1&&i+j!=k) continue;
                        ans+=dp[mx-1][k][i][j];
                    }
        cout<<"Case "<<cas++<<": "<<ans<<endl;
        memset(cpp,0,sizeof(cpp));
    }
    return 0;
}

HDOJ 4249 A Famous Equation DP

原文：http://blog.csdn.net/ck_boss/article/details/40272459