सी ++ में ऐरे को पुनर्स्थापित करें

मान लीजिए कि एक प्रोग्राम है जो किसी एरे ए के ऐरे एलिमेंट्स को प्रिंट करने के लिए उपयोग किया जाता है, लेकिन प्रोग्राम में थोड़ी सी गलती थी। उस कार्यक्रम में प्रत्येक तत्व के बाद कोई सफेद स्थान नहीं था, इसलिए यदि हमारे पास एक मुद्रित स्ट्रिंग है, तो क्या हम फिर से सरणी को पुन:उत्पन्न कर सकते हैं? हम जानते हैं कि सरणी तत्व 1 से k की सीमा में हैं।

स्ट्रिंग s और पूर्णांक k को देखते हुए। हमें यह पता लगाना है कि हम कितने तरीकों से सरणी को पुनर्स्थापित कर सकते हैं। उत्तर बहुत बड़ा हो सकता है इसलिए इसे मॉड्यूलो 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट S ="1318" और k =2000 जैसा है, तो आउटपुट 8 होगा, क्योंकि हम [1318], [131,8], [13,18], [1,318] जैसे 8 अलग-अलग सरणियाँ बना सकते हैं। ],[1,3,18],[1,31,8],[13,1,8],[1,3,1,8]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

कॉन्स्ट इंट एम =1e9 + 7
एक मानचित्र डीपी परिभाषित करें
फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
. लगेगा
वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम
फ़ंक्शन सहायता () को परिभाषित करें, इसमें idx, s, num, k,
लगेगा
अगर idx>=s का आकार, तो −
- वापसी 1
अगर idx dp में है और num dp[idx] में है, तो -
- वापसी डीपी [आईडीएक्स, संख्या]
रिट:=0
अगर num>=1 और num>=k और s[idx] '0' के बराबर नहीं है, तो -
- ret :=add(help(idx, s, 0, k), ret)
यदि संख्या * 10 + (s[idx] - '0') <=k, तो -
- ret :=add(help(idx + 1, s, num * 10 + (s[idx] - ASCII of '0'), k), ret)
dp[idx, num] :=ret
वापसी रिट
मुख्य विधि से निम्न कार्य करें -
n :=s का आकार
आकार n + 1
. के एक सरणी उत्तर को परिभाषित करें
ans[0] :=1
s :=s से पहले एक सफेद स्थान को संयोजित करें
ks :=k को स्ट्रिंग में बदलें
इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -
- सीएनटी:=1
- अस्थायी:=रिक्त स्ट्रिंग
- प्रारंभ करने के लिए j :=i, जब j>=1 और cnt <=10, अपडेट करें (j को 1 से घटाएं), (1 से cnt बढ़ाएं), करें -
  - अस्थायी:=एस [जे] + अस्थायी
  - यदि s[j] '0' के समान है, तो -
    - निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
  - यदि अस्थायी का आकार> ks का आकार, तो -
    - लूप से बाहर आएं
  - वैल:=संख्या के रूप में अस्थायी
  - अगर वैल>=1 और वैल <=के, तो -
    - ans[i] :=add(ans[i], ans[j - 1])
वापसी उत्तर [n]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
   public:
   unordered_map<int, unordered_map<lli, int> > dp;
   lli add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int help(int idx, string& s, lli num, int k){
      if (idx >= s.size())
      return 1;
      if (dp.count(idx) && dp[idx].count(num))
      return dp[idx][num];
      int ret = 0;
      if (num >= 1 && num <= k && s[idx] != '0') {
         ret = add(help(idx, s, 0, k), ret);
      }
      if (num * 10 + (s[idx] - '0') <= k) {
         ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k),
         ret);
      }
      return dp[idx][num] = ret;
   }
   int numberOfArrays(string s, int k){
      int n = s.size();
      vector<lli> ans(n + 1);
      ans[0] = 1;
      s = " " + s;
      string ks = to_string(k);
      for (lli i = 1; i <= n; i++) {
         lli cnt = 1;
         string temp = "";
         for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
            temp = s[j] + temp;
            if (s[j] == '0')
               continue;
            if (temp.size() > ks.size())
            break;
            lli val = stol(temp);
            if (val >= 1 && val <= k) {
               ans[i] = add(ans[i], ans[j - 1]);
            }
         }
      }
      return ans[n];
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfArrays("1318",2000));
}

इनपुट

"1318", 2000