本文涉及知识点

C++动态规划

LeetCode2466. 统计构造好字符串的方案数

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：
将 ‘0’ 在字符串末尾添加 zero 次。
将 ‘1’ 在字符串末尾添加 one 次。
以上操作可以执行任意次。
如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。
请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。
示例 1：
输入：low = 3, high = 3, zero = 1, one = 1
输出：8
解释：
一个可能的好字符串是 “011” 。
可以这样构造得到：“” -> “0” -> “01” -> “011” 。
从 “000” 到 “111” 之间所有的二进制字符串都是好字符串。
示例 2：
输入：low = 2, high = 3, zero = 1, one = 2
输出：5
解释：好字符串为 “00” ，“11” ，“000” ，“110” 和 “011” 。
提示：
1 <= low <= high <= 10⁵
1 <= zero, one <= low

动态规划

动态规划的状态表示

dp[i]表示，通过以上方式创建长度为i的字符串数量。i$\in$[0,high]。
空间复杂度：O(high)

动态规划的转移方程

前置状态更新后续状态。
dp[i+zero] += dp[i]
dp[i+one] += dp[i]
注意：需要判断i+zero和 i+one 是否小于等于hight。
单个状态转移的时间复杂度：O(1)。总时间复杂度：O(high)

动态规划的填表顺序

i = 0 to high-1

动态规划的初始值

dp[0]=1，其它全为0。

动态规划的返回值

dp[low…high]之和。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator/(const C1097Int& o)const
	{
		return *this * o.PowNegative1();
	}
	C1097Int& operator/=(const C1097Int& o)
	{
		*this /= o.PowNegative1();
		return *this;
	}
	bool operator==(const C1097Int& o)const
	{
		return m_iData == o.m_iData;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};


class Solution {
		public:
			int countGoodStrings(int low, int high, int zero, int one) {
				vector<C1097Int<>> dp(high + 1);
				dp[0] = 1;
				for (int i = 0; i < high; i++) {
					if (i + zero <= high) {
						dp[i + zero] += dp[i];
					}
					if (i + one <= high) {
						dp[i + one] += dp[i];
					}
				}
				C1097Int<> ans = accumulate(dp.begin() + low, dp.end(), C1097Int<>());
				return ans.ToInt();
			}
		};

单元测试

int low,  high,  zero,  one;
		TEST_METHOD(TestMethod11)
		{
			low = 3, high = 3, zero = 1, one = 1;
			auto res = Solution().countGoodStrings(low, high, zero, one);
			AssertEx(8, res);
		}
		TEST_METHOD(TestMethod12)
		{
			low = 2, high = 3, zero = 1, one = 2;
			auto res = Solution().countGoodStrings(low, high, zero, one);
			AssertEx(5, res);
		}