本文涉及知识点

C++动态规划 状态机dp

LeetCode2266. 统计打字方案数

Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。
为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。
比方说，为了按出字母 ‘s’ ，Alice 需要按 ‘7’ 四次。类似的， Alice 需要按 ‘5’ 两次得到字母 ‘k’ 。
注意，数字 ‘0’ 和 ‘1’ 不映射到任何字母，所以 Alice 不 使用它们。
但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。
比方说，Alice 发出的信息为 “bob” ，Bob 将收到字符串 “2266622” 。
给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。
由于答案可能很大，将它对 10⁹ + 7 取余 后返回。
示例 1：
输入：pressedKeys = “22233”
输出：8
解释：
Alice 可能发出的文字信息包括：
“aaadd”, “abdd”, “badd”, “cdd”, “aaae”, “abe”, “bae” 和 “ce” 。
由于总共有 8 种可能的信息，所以我们返回 8 。
示例 2：
输入：pressedKeys = “222222222222222222222222222222222222”
输出：82876089
解释：
总共有 2082876103 种 Alice 可能发出的文字信息。
由于我们需要将答案对 10⁹ + 7 取余，所以我们返回 2082876103 % (10⁹ + 7) = 82876089 。
提示：
1 <= pressedKeys.length <= 10⁵
pressedKeys 只包含数字 ‘2’ 到 ‘9’ 。

动态规划

n = pressedKeys.length

动态规划的状态表示

dp[i]表示 s[0…i] 的所有方案数。空间复杂度：O(n)

动态规划的转移方程

枚举后续状态。
dp[i] += dp[i-1]
如果dp[0…i-1]的后两个字符相等：
dp[i] += dp[i-2];
三个字符相同和四个字符相等，类似。注意：7和9可以按4次，其它只能按三次。
单个状态转移的时间复杂度是O(1)，总时间复杂度：O(n)。

动态规划的初始值

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

动态规划的填表顺序

i = i To n

动态规划的返回值

dp.back()

代码

核心代码

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 countTexts(string s) {
				const int N = s.length();
				vector<C1097Int<>> dp(N + 1);
				dp[0] = 1;
				for (int i = 1; i <= N; i++) {
					dp[i] += dp[i - 1];
					if ((i - 2 < 0) || (s[i - 2] != s[i - 1])) { continue; }
					dp[i] += dp[i - 2];
					if ((i - 3 < 0) || (s[i - 3] != s[i - 1])) { continue; }
					dp[i] += dp[i - 3];
					if (('7' != s[i - 1]) && ('9' != s[i - 1]))continue;
					if ((i - 4 < 0) || (s[i - 4] != s[i - 1])) { continue; }
					dp[i] += dp[i - 4];
				}
				return dp.back().ToInt();
			}
		};

单元测试

string pressedKeys;
		TEST_METHOD(TestMethod11)
		{
			pressedKeys = "22233";
			auto res = Solution().countTexts(pressedKeys);
			AssertEx(8, res);
		}
		TEST_METHOD(TestMethod12)
		{
			pressedKeys = "222222222222222222222222222222222222";
			auto res = Solution().countTexts(pressedKeys);
			AssertEx(82876089, res);
		}