我们将看一个问题，其中给定一个整数字符串，并且必须确定有多少子字符串可以被整数格式的 6 整除。需要注意的是，输入是由数字（整数）组成的字符串形式。尽管如此，除法检查将仅将其视为整数（不使用字符串输入的 ASCII 值）。
输入
str = “648”
解释
子字符串“6”、“48”和“648”可以被 6 整除。
输入
str = “38342”
输出
4
解释
子字符串“3834”、“342”、“834”和“42”可以被 6 整除。
蛮力方法
用户可以检查每个可能的子字符串，看看它是否能被 6 整除。如果子字符串是可整除的，我们额外计算它。这种方法将需要更长的时间来解决问题，并且需要 O(n2) 时间来完成任务。
示例
#include <bits/stdc++.h>
using namespace std;
int
str_to_int (string str, int i, int j) {
int temp = 0;
for (; i <= j; i++) {
temp = temp * 10 + (str[i] - '0');
}
return temp;
}
int main () {
char str[] = "24661";
int n = strlen (str);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = str_to_int (str, i, j);
if (temp % 6 == 0) count++;
}
}
cout << count << endl;
return 0;
}输出结果6
高效的方法
一个数字的最后一位数字必须能被 2 整除才能被 6 整除。数字的总数应该是 3。通过跟踪先前计算的答案，我们可以利用动态规划来发现解决方案。
Let f(i,s)- 来自第 i 个索引的字符串数，其数字和模 3 为 s，得到 Σin-1 f(i,0)。
设 a 为字符串的第 i 位；现在，从 开始f(i,s)，我们需要找到所有偶数且以 i + 1 开头的子串。如果 (a+s) 可被 3 整除，则可以产生额外的子串。于是，我们的递推关系就形成了，
f(i,s)= f(i + 1, (s + a)%3) + (a%2 == 0 AND (a+s)%3 == 0)。
示例 2
#include <bits/stdc++.h>
using namespace std;
int find(int i, int s, char str[], int dp[][3]){
//当到达字符串末尾时。
if (i == strlen(str))
return 0;
//如果已经计算，则返回结果。
if (dp[i][s] != -1)
return dp[i][s];
int a = str[i] - '0';
int ans = ((a+s)%3 == 0 && a%2 == 0) + find(i+1, (s+a)%3, str, dp);
return dp[i][s] = ans;
}
int main(){
char str[] = "24661";
int n = strlen(str);
//dp 数组来存储所有状态。
int dp[n+1][3];
memset(dp, -1, sizeof dp);
int count = 0;
for (int i = 0; i < n; i++){
//如果任何位置包含 0 增量计数。
if (str[i] == '0')
count++;
//将先前的 sum modulo 3 = 0 传递给递归函数。
else
count += find(i, 0, str, dp);
}
cout << "可被 6 整除的子串数： " << count << endl;
return 0;
}输出结果可被 6 整除的子串数： 6
时间复杂度：O(N)
结论
在本教程中，我们学习了如何使用动态规划来发现整数字符串中可被 6 整除的子字符串的数量。同一个程序可以用不同的语言编写，例如 C、Java、Python 等。我们希望您发现本课程对您有所帮助。
