【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

template<class ELE, class ResultType, ELE minEle, ELE maxEle>
class CLowUperr
{
public:
  CLowUperr(int iResutlCount) :m_iResutlCount(iResutlCount)
  {
  }
  void Init(const ELE* pLower, const ELE* pHigh, int iNum)
  {
    m_vPre.assign(4, vector<ResultType>(m_iResutlCount));
    if (iNum <= 0)
    {
      return;
    }
    InitPre(pLower, pHigh);
    iNum--;
    while (iNum--)
    {
      pLower++;
      pHigh++;
      vector<vector<ResultType>> dp(4, vector<ResultType>(m_iResutlCount));
      OnInitDP(dp);
      //处理非边界
      for (auto tmp = minEle; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[0], tmp);
      }
      //处理下边界
      OnEnumOtherBit(dp[1], m_vPre[1], *pLower);
      for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[1], tmp);
      }
      //处理上边界
      OnEnumOtherBit(dp[2], m_vPre[2], *pHigh);
      for (auto tmp = minEle; tmp < *pHigh; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[2], tmp);
      }
      //处理上下边界
      if (*pLower == *pHigh)
      {
        OnEnumOtherBit(dp[3], m_vPre[3], *pLower);
      }
      else
      {
        OnEnumOtherBit(dp[1], m_vPre[3], *pLower);
        for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++)
        {
          OnEnumOtherBit(dp[0], m_vPre[3], tmp);
        }
        OnEnumOtherBit(dp[2], m_vPre[3], *pHigh);
      }
      m_vPre.swap(dp);
    }
  }
  /*ResultType Total(int iMinIndex, int iMaxIndex)
  {
    ResultType ret;
    for (int status = 0; status < 4; status++)
    {
      for (int index = iMinIndex; index <= iMaxIndex; index++)
      {
        ret += m_vPre[status][index];
      }
    }
    return ret;
  }*/
protected:
  const int m_iResutlCount;
  void InitPre(const ELE* const pLower, const ELE* const pHigh)
  {
    for (ELE cur = *pLower; cur <= *pHigh; cur++)
    {
      int iStatus = 0;
      if (*pLower == cur)
      {
        iStatus = *pLower == *pHigh ? 3 : 1;
      }
      else if (*pHigh == cur)
      {
        iStatus = 2;
      }
      OnEnumFirstBit(m_vPre[iStatus], cur);
    }
  }
  virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue) = 0;
  virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue) = 0;
  virtual void OnInitDP(vector<vector<ResultType>>& dp)
  {
  }
  vector<vector<ResultType>> m_vPre;
};
class CCharLowerUper : public CLowUperr<char, pair<int, int>, '0', '9'>
{
public:
  CCharLowerUper():CLowUperr(1<<10)
  {
  }
  int Total()
  {
    return Total(0, m_iResutlCount-1);
  }
  int Total(int iMinIndex, int iMaxIndex)
  {
    int ret = 0;
    for (int index = iMinIndex; index <= iMaxIndex; index++)
    {
      int cur = 0;
      for (int status = 0; status < 4; status++)
      {
        cur += m_vPre[status][index].second;
      }
      ret += cur;
    }
    return ret;
  }
protected:
  virtual void OnEnumFirstBit(vector<pair<int, int>>& vPre, const char curValue)
  {
    const int index = curValue - '0';
    vPre[1 << index].first = 1; 
  }
  virtual void OnEnumOtherBit(vector<pair<int, int>>& dp, const vector<pair<int, int>>& vPre, char curValue)
  {
    const int index = curValue - '0';
    for (int i = 0; i < m_iResutlCount; i++)
    {
      const int iNewMask = (1 << index) | i;
      if (iNewMask == i )
      {
        dp[iNewMask].second += vPre[i].first + vPre[i].second;
      }
      else
      {
        dp[iNewMask].first += vPre[i].first;
        dp[iNewMask].second +=  vPre[i].second;
      }
    }
  }
};
class Solution {
public:
  int numDupDigitsAtMostN(int n) {
    const string strN = std::to_string(n);
    const int len = strN.length();
    int iRet = 0;
    for (int i = 1; i < len; i++)
    {
      CCharLowerUper lu;
      lu.Init(("1" + string(i - 1, '0')).c_str(), string(i, '9').c_str(), i);
      iRet += lu.Total();
    }
    CCharLowerUper lu;
    lu.Init(("1" + string(len - 1, '0')).c_str(), strN.c_str(), len);
    iRet += lu.Total();
    return iRet;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  int n;
  {
    Solution sln;
    n = 20;
    auto res = sln.numDupDigitsAtMostN(n);
    Assert(res, 1);
  }
  {
    Solution sln;
    n = 100;
    auto res = sln.numDupDigitsAtMostN(n);
    Assert(res, 10);
  }
  {
    Solution sln;
    n = 1000;
    auto res = sln.numDupDigitsAtMostN(n);
    Assert(res, 262);
  }
}