LeetCode 2719. 统计整数数目,数位dp板子题

发布时间:2024年01月16日

一、题目

1、题目描述

给你两个数字字符串?num1?和?num2?,以及两个整数?max_sum?和?min_sum?。如果一个整数?x?满足以下条件,我们称它是一个好整数:

  • num1 <= x <= num2
  • min_sum <= digit_sum(x) <= max_sum.

请你返回好整数的数目。答案可能很大,请返回答案对?109 + 7?取余后的结果。

注意,digit_sum(x)?表示?x?各位数字之和。

2、接口描述

?
class Solution {
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        
    }
};

3、原题链接

2719. 统计整数数目


二、解题报告

1、思路分析

数位dp板子题

数位dp详见:数位dp详解,记忆化搜索,递推,OJ精讲-CSDN博客

设计状态f[n][pre][lim]为剩余n位,n位之前的数位和为pre,前面枚举位和给定数字对应位大小关系为lim

那么转移方程为f[n][pre][lim] = Σdfs(n - 1 , pre + i , lim || i < ceil) , 其中ceil = lim ? 9 : d[n]

跑板子即可,确实没什么说的,只要学过数位dp很容易就套板子套出来了

由于给出的数字是高精度字符串,所以对于小的那个数字-1的时候按照高精度的处理方式来,细节处理好

2、复杂度

时间复杂度: O(n * 9 * n * 9) 空间复杂度:O(n * 9 * n)

3、代码详解

?
class Solution
{
public:
#define N 24
	typedef long long ll;
	const ll MOD = 1e9 + 7;
	ll f[N][N * 9];
	int r, l, d[N], len, n1, n2;
	Solution() { memset(f, -1, sizeof(f)); }
	int count(string num1, string num2, int min_sum, int max_sum)
	{
		function<int(int, int, bool)> dfs = [&](int n, int pre, bool lim) -> int
		{
			if (!n)
				return pre >= min_sum && pre <= max_sum;
			if (lim && ~f[n][pre])
				return f[n][pre];
			ll res = 0, ceil = lim ? 9 : d[n];
			for (int i = 0; i <= ceil; i++)
				res = (res + dfs(n - 1, pre + i, lim || i < ceil)) % MOD;
			if (lim)
				return f[n][pre] = res;
			return res;
		};
		n2 = num2.size(), n1 = num1.size() , len = 0;
		while (n2--)
			d[++len] = (num2[n2] ^ 48);
		r = dfs(len, 0, false);
		len = 0;
		while (n1--)
			d[++len] = (num1[n1] ^ 48);
		n1 = 1;
		d[1]--;
		while (n1 <= len && d[n1] == -1)
			d[n1++] += 10, d[n1]--;
		l = dfs(len, 0, false);
		return (r - l + MOD) % MOD;
	}
};

文章来源:https://blog.csdn.net/EQUINOX1/article/details/135623501
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。