title: Digit Dynamic Programming Problem For Sum of Numbers
body: <p>I want to find the sum of all the positive integers in the range [1, N] with a given digit sum d. For example, if n = 100 and d = 7, the answer will be 7 + 16 + 25 + 34 + 43 + 52 + 61 + 70 = 308.</p>
  <p>Following code can be used to count the numbers in the range [1, N] with a given digit sum d.</p>
  <p>cnt[i][0][s] denotes count of suffixes that can be formed starting from index i, whose digits add up to s.</p>
  <p>cnt[i][1][s] count of suffixes that can be formed starting from index i, whose digits add up to s such that the formed suffix is not greater than corresponding suffix in input string</p>
  <pre><code>#include &lt;bits/stdc++.h&gt;
  
  using namespace std;
  
  typedef long long int i64;
  
  i64 cnt[20][2][200];
  
  void digit_sum_dp(string ss) {
      int n = ss.size();
  
      for (int i = 0; i &lt; 20; i++) {
          for (int j = 0; j &lt; 2; j++) {
              for (int k = 0; k &lt; 200; k++) {
                  cnt[i][j][k] = 0;
              }
          }
      }
  
      cnt[n][0][0] = 1;
      cnt[n][1][0] = 1;
   
      for (int i = n - 1; i &gt;= 0; i--) {
          for (int tight = 0; tight &lt; 2; tight++) {
              for (int sum = 0; sum &lt; 200; sum++) {
                  if (tight) {
                      for (int d = 0; d &lt;= ss[i] - '0'; d++) {
                          if (d == ss[i] - '0') {
                              cnt[i][1][sum] += cnt[i + 1][1][sum - d];
                          } else {
                              cnt[i][1][sum] += cnt[i + 1][0][sum - d];
                          }
                      }
                  } else {
                      for (int d = 0; d &lt; 10; d++) {
                          cnt[i][0][sum] += cnt[i + 1][0][sum - d];
                      }
                  }
              }
          }
      }
      return cnt[0][1][d];
  }
  
  int main() {
      string str = &quot;100&quot;;
      int d = 7;
      cout &lt;&lt; digit_sum_dp(str, d) &lt;&lt; &quot;\n&quot;;
      return 0;
  }
  </code></pre>
  <p>I have tried to extend the code to find out the sum of numbers instead of the count of numbers. Following is a code snippet.</p>
  <pre><code>cnt[i][1][sum] += cnt[i + 1][1][sum - d];
  tot[i][1][sum] += (d * cnt[i + 1][1][sum - d] + tot[i + 1][1][sum - d] * pow(10, i));
  </code></pre>
  <p>I am getting incorrect results for some of the inputs. I shall be grateful if someone can help me.</p>