【状态压缩】【动态规划】【C++算法】691贴纸拼词-Toy模板网

这篇具有很好参考价值的文章主要介绍了【状态压缩】【动态规划】【C++算法】691贴纸拼词。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

状态压缩

LeetCode:691 贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
示例 1：
输入： stickers = [“with”,“example”,“science”], target = “thehat”
输出：3
解释：
我们可以使用 2 个 “with” 贴纸，和 1 个 “example” 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。
示例 2:
输入：stickers = [“notice”,“possible”], target = “basicbasic”
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:
n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target.length <= 15
stickers[i] 和 target 由小写英文单词组成

封装类

假定target串有个n1字符，数量分别为m_vMax[0] m_vMax[1]…m_vMax[n1-1]。
对于某个stickers串，忽略target中没有的字符。target第0 1 2… 个字符在sticker的数量为vNum[0],vNum[1]…
则第0个字符的mask为1*vNum[0]
第1个字符的mask为(m_vMax[0]+1)*vNum[1]
…
第i个字符的mask为：Mul $\Large^j_{[0,i-1]}$ (vMax[j]+1)*vNum[i]
总mask 为各字符mask之和。
注意：无论如何vNum[i]都大于等于0，小于等于m_vMax[i]

class CMask
{
public:
	void Add(int iMax)//当前最高位范围[0,iMax]
	{
		m_vMax.emplace_back(iMax);
		m_iMaskCount *= (iMax + 1);
	}
	vector<int> FromMask(int iMask)
	{
		vector<int> vNums;
		for (int i = 0; i < m_vMax.size(); i++)
		{
			vNums.emplace_back(iMask % (m_vMax[i] + 1));
			iMask /= (m_vMax[i] + 1);
		}
		return vNums;
	}
	int ToMask(const vector<int>& vNums,int iMul=1)
	{
		int iMask = 0;
		int iUnit = 1;
		for (int i = 0; i < m_vMax.size(); i++)
		{
			iMask += iUnit * min(m_vMax[i],vNums[i]* iMul);
			iUnit *= (m_vMax[i]+1);
		}
		return iMask;
	}
	int MaskSubVector(int iMask, const vector<int>& vNums, const int iMul = 1)
	{
		int iNewMask = 0;
		int iUnit = 1;
		for (int i = 0; i < m_vMax.size(); i++)
		{
			int cur = iMask % (m_vMax[i] + 1);
			cur -= vNums[i] * iMul;
			cur = max(0, cur);
			iNewMask += iUnit * cur;
			iMask /= (m_vMax[i] + 1);
			iUnit *= (m_vMax[i]+1);
		}
		return iNewMask;
	}
	int NeedGroupCount(const vector<int>& need, const vector<int>& has)
	{
		int iMax = 0;
		for (int i = 0; i < m_vMax.size(); i++)
		{
			if (has[i] <= 0)
			{
				continue;
			}
			iMax = max(iMax,need[i] / has[i]+ (0 != need[i] % has[i]));
		}
		return iMax;
	}
public:
	int MaskCount()const
	{
		return m_iMaskCount;
	}	
	int BitCount()const
	{
		return m_vMax.size();
	}
protected:
	int m_iMaskCount = 1;
	vector<int> m_vMax;
};

class CStrMask : public CMask
{
public:
	CStrMask(const string& target)
	{
		vector<int> vCount;
		for (const auto& ch : target)
		{
			if (mCharToIndex.count(ch))
			{
				vCount[mCharToIndex[ch]]++;
			}
			else
			{
				mCharToIndex[ch] = vCount.size();
				vCount.emplace_back(1);
			}
		}
		for (const auto& cnt : vCount)
		{
			CMask::Add(cnt);
		}
	}
	vector<int> GetVector(const string& s )
	{
		vector<int> vCharNums(m_vMax.size());
		for (const char& ch : s)
		{
			if (mCharToIndex.count(ch))
			{
				auto& i = vCharNums[mCharToIndex[ch]];
				if (i < m_vMax[mCharToIndex[ch]])
				{
					i++;
				}				
			}
		}
		return vCharNums;
	}
protected:
	unordered_map<char, int> mCharToIndex;
private:
	void Add(int iMax) {};
};

动态规划

动态规划的状态表示

pre[iMask] 表示利用前i-1个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。1000表示无法达成。
dp[iMask] 表示利用前i 个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。

动态规划的转移方程

iPreMask 当前贴纸使用的贴纸数量如果状态发生变化，则更新状态。

动态规划的填表顺序

对于每个合法的iPreMask，计算当前贴纸最多需要多少份。三层循环：第一层，枚举各贴纸。第二层，枚举pre各状态。第三层：枚举当前贴纸使用的数量。每次处理还要枚举各字符。
故总时间复杂度为：O(50*2¹⁵1515)

动态规划的初始状态

pre[iMaskCount-1=0 其它值为1000。

动态规划的返回值

pre[0]

代码

核心代码

class Solution {
public:
	int minStickers(vector<string>& stickers, string target) {
		CStrMask mask(target);
		vector<vector<int>> vMaskToCounts(mask.MaskCount());
		for (int i = 0; i < mask.MaskCount(); i++)
		{
			vMaskToCounts[i] = mask.FromMask(i);
		}
		vector<int> vPre(mask.MaskCount(), 1000);
		vPre[mask.MaskCount() - 1] = 0;
		for (const auto s : stickers)
		{
			auto vCharNums = mask.GetVector(s);
			vector<int> dp = vPre;//不选择
			for (int iPre = 0; iPre < mask.MaskCount(); iPre++)
			{
				if (vPre[iPre] >= 1000)
				{
					continue;
				}
				const int iSelMax = mask.NeedGroupCount(vMaskToCounts[iPre], vCharNums);
				for (int iSel = 1; iSel <= iSelMax; iSel++)
				{
					const int iNewMask = mask.MaskSubVector(iPre, vCharNums, iSel);
					dp[iNewMask] = min(dp[iNewMask], vPre[iPre] + iSel);
				}
			}
			vPre.swap(dp);
		}
		return (vPre[0] >= 1000) ? -1 : vPre[0];
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}





int main()
{
	

	vector<string> stickers;
	string target;
	{
		Solution sln;
		stickers = { "travel", "quotient", "nose", "wrote", "any" }, target = "lastwest";
		auto res = sln.minStickers(stickers, target);
		Assert(4, res);
	}
	{
		Solution sln;
		stickers = { "with", "example", "science" }, target = "thehat";
		auto res = sln.minStickers(stickers, target);
		Assert(3, res);
	}
	{
		Solution sln;
		stickers = { "notice", "possible" }, target = "basicbasic";
		auto res = sln.minStickers(stickers, target);
		Assert(-1, res);
	}

	{
		Solution sln;
		stickers = { "right", "ten", "year", "share", "period", "paper", "expect", "village", "home", "happen", "ring", "sat", "even", "afraid", "paint", "self", "range", "camp", "note", "read", "paragraph", "run", "basic", "fill", "week", "his", "star", "power", "any", "colony", "object", "free", "dark", "said", "chick", "true", "glad", "child", "room", "lost", "am", "cry", "quiet", "crease", "while", "race", "fun", "found", "dream", "once" }, target = "materialhalf";
		auto res = sln.minStickers(stickers, target);
		Assert(4, res);
	}

	{
		Solution sln;
		stickers = { "indicate","why","finger","star","unit","board","sister","danger","deal","bit","phrase","caught","if","other","water","huge","general","read","gold","shall","master","men","lay","party","grow","view","if","pull","together","head","thank","street","natural","pull","raise","cost","spoke","race","new","race","liquid","me","please","clear","could","reply","often","huge","old","nor" }, target = "fhhfiyfdcwbycma";
		auto res = sln.minStickers(stickers, target);
		Assert(9, res);
	}
	
}

改进简洁版，性能略差

不区分dp pre，因为一个贴纸可以无限使用。无论是pre[iMask]和dp[iMask] 都可增加贴纸。

动态规划的状态表示

状态压缩：如果target第i位已经贴好，则此位为1；否则此位为0。
dp[iMask] 已经完成iMask 消耗的最少贴纸数。

动态规划的转移方程。

对应每个mask，只需要考虑一个当前贴纸。比如：目标串为aaa，贴纸为a。状态0只考虑一个贴纸。状态1只考虑1个贴纸，总共2个贴纸。状态3只考虑1个贴纸，总共3个贴纸。
如果目标串有多个相同字符，只需要匹配第一字符。“???” 第一张贴纸后，变成"a??" 不需要考虑“?a?"
方案一：第i步匹配第1个a，第j个步匹配第2个a。
方案二：第i步匹配第2个a，第j个步匹配第1个a。
如果方案二，能达到目标，那方案一显然也能达到目标。
iPreMask等于iNewMask 也不用排除，因为新值比旧值大1，必定被淘汰。

class Solution {
public:
	int minStickers(vector<string>& stickers, string target) {
		const int iMaskCount = 1 << target.size();
		vector<int> dp(iMaskCount, 1000);
		dp[0] = 0;
		for (const auto s : stickers)
		{
			int cnt1[26] = { 0 };
			for (const auto& ch : s)
			{
				cnt1[ch - 'a']++;
			}
			for (int iPreMask = 0; iPreMask < iMaskCount; iPreMask++)
			{
				int cnt[26] = { 0 };
				memcpy(cnt, cnt1, sizeof(cnt1));
				int iNewMask = iPreMask;
				for (int j = 0; j < target.size(); j++)
				{
					if (iPreMask & (1 << j))
					{
						continue;//已经拼成
					}
					if (cnt[target[j] - 'a'])
					{
						cnt[target[j] - 'a']--;
						iNewMask |= (1 << j);
					}
				}
				dp[iNewMask] = min(dp[iNewMask], dp[iPreMask] + 1);
			}		
		}
		return (dp.back() >= 1000) ? -1 : dp.back();
	}
};

2023年1月第一版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
for (auto& ch : target)
{
m_mTarget[ch]++;
}
std::unordered_set hasMask;
hasMask.insert(0);
std::unordered_map<int,int> preMaskNum;
preMaskNum[0] = 0;
for (auto& s : stickers)
{
std::unordered_map<char, int> mCur;
for (auto& ch : s)
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
std::unordered_map<int, int> dp = preMaskNum;
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
for (const auto& preMask : preMaskNum )
{
std::unordered_map<char, int> mPre;
ParseMask(mPre, preMask.first);
bool bAdd = true;
int iNum = preMask.second;
while (bAdd)
{
bAdd = false;
for (const auto it : mCur)
{
if (m_mTarget[it.first] > mPre[it.first])
{
bAdd = true;
mPre[it.first] = min(m_mTarget[it.first], mPre[it.first] + mCur[it.first]);
}
}
if (bAdd)
{
iNum++;
const int iMask = MakeMask(mPre);
if (dp.count(iMask))
{
dp[iMask] = min(dp[iMask], iNum);
}
else
{
dp[iMask] = iNum;
}
}
}
}
preMaskNum.swap(dp);
}
int iMaskTargt = MakeMask(m_mTarget);
if (preMaskNum.end() == preMaskNum.find(iMaskTargt))
{
return -1;
}
return preMaskNum[iMaskTargt];
}
int MakeMask(const std::unordered_map<char, int>& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map<char, int>& nums, int iMask)
{
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second+1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second+1);
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
std::string m_target;
std::unordered_map<char, int> m_mTarget;
};

2023年1月第2版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();
vector<std::unordered_map<char, int>> mAllCharNum;
{
std::unordered_set hasMask;
hasMask.insert(0);
for (int i = stickers.size() - 1; i >= 0; i–)
{
std::unordered_map<char, int> mCur;
for (auto& ch : stickers[i])
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
mAllCharNum.push_back(mCur);
}
}
std::unordered_set setPreMask,setHasDo;
setPreMask.insert(m_iTargetMask);
setHasDo.insert(m_iTargetMask);
for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
{
std::unordered_set dp;
for (auto& preMask : setPreMask)
{
std::unordered_map<char, int> mPre;
ParseMask(mPre, preMask);
for (auto& mCur : mAllCharNum)
{
const int iSubMask = GetSubMask(mPre, mCur);
if (0 == iSubMask)
{
continue;
}
const int iNewMask = preMask - iSubMask;
if (setHasDo.count(iNewMask))
{
continue;
}
if (iNewMask == 0 )
{
return iOpeNum;
}
setHasDo.insert(iNewMask);
dp.insert(iNewMask);
}
}
setPreMask.swap(dp);
vector<std::unordered_map<char, int>> mAllTmp;
for (auto& it : setPreMask)
{
std::unordered_map<char, int> tmp;
ParseMask(tmp, it);
mAllTmp.push_back(tmp);
}
}
return -1;
}
int GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur)
{
int iSubMask = 0;
for (auto& cur : mCur)
{
auto pre = mPre.find(cur.first);
if (pre->second )
{
iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-‘a’];
}
}
return iSubMask;
}
int MakeMask(const std::unordered_map<char, int>& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map<char, int>& nums, int iMask)
{
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
const int iMul = m_vCharMul[it->first-‘a’];
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
void Init()
{
for (auto& ch : m_target)
{
m_mTarget[ch]++;
}
m_iTargetMask = MakeMask(m_mTarget);
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second + 1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second + 1);
m_vCharMul[it->first - ‘a’] = iMul;
}
}
std::string m_target;
int m_iTargetMask;
std::unordered_map<char, int> m_mTarget;
int m_vCharMul[26] ;
};

2023年1月第三版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();

	 vector<std::unordered_map<char, int>> mAllCharNum;
	 {
		 std::unordered_set<int> hasMask;
		 hasMask.insert(0);
		 for (int i = stickers.size() - 1; i >= 0; i--)
		 {
			 std::unordered_map<char, int> mCur;
			 for (auto& ch : stickers[i])
			 {
				 if (m_mTarget.count(ch))
				 {
					 mCur[ch]++;
				 }
			 }
			 const int iCurMask = MakeMask(mCur);
			 if (hasMask.count(iCurMask))
			 {
				 continue;
			 }
			 hasMask.insert(iCurMask);
			 mAllCharNum.push_back(mCur);
		 }
	 }
	
	 std::unordered_set<int> setPreMask,setHasDo;
	 setPreMask.insert(m_iTargetMask);
	 setHasDo.insert(m_iTargetMask);
	 for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
	 {
		 std::unordered_set<int> dp;
		 for (auto& preMask : setPreMask)
		 {
			 std::unordered_map<char, int> mPre;
			 ParseMask(mPre, preMask);
			 
			 char chFristNeedChar = 0;
			 for (auto& it : mPre)
			 {
				 if (it.second > 0)
				 {
					 chFristNeedChar = it.first;
					 break;
				 }
			 }

			 for (auto& mCur : mAllCharNum)
			 {
				 if ((0 == mCur.count(chFristNeedChar)) || (mCur[chFristNeedChar] <= 0 ))
				 {
					 continue;
				 }

				 const int iSubMask = GetSubMask(mPre, mCur);
				 if (0 == iSubMask)
				 {
					 continue;
				 }
				 const int iNewMask = preMask - iSubMask;
				 if (setHasDo.count(iNewMask))
				 {
					 continue;
				 }
				 if (iNewMask == 0 )
				 {
					 return iOpeNum;
				 }
				 setHasDo.insert(iNewMask);
				 dp.insert(iNewMask);
			 }
		 }
		 setPreMask.swap(dp);

		 vector<std::unordered_map<char, int>> mAllTmp;
		 for (auto& it : setPreMask)
		 {
			 std::unordered_map<char, int> tmp;
			 ParseMask(tmp, it); 
			 mAllTmp.push_back(tmp);
		 }
	 }
	 
	 
	 return -1;
 }
 int GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur)
 {
	 int iSubMask = 0;
	 for (auto& cur : mCur)
	 {
		 auto pre = mPre.find(cur.first);
		 if (pre->second )
		 {
			 iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-'a'];
		 }
	 }
	 return iSubMask;
 }
 int MakeMask(const std::unordered_map<char, int>& nums)const
 {
	 int iMask = 0;
	 for (const auto& mm : m_mTarget )
	 {
		 auto it = nums.find(mm.first);
		 if ((nums.end() != it) && ( it->second > 0 ))			
		 {
			 iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
		 }
		 else
		 {
			 iMask = iMask * (mm.second + 1);
		 }
	 }
	 return iMask;
 }
 void ParseMask(std::unordered_map<char, int>& nums, int iMask)
 {
	 for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
	 {
		 const int iMul = m_vCharMul[it->first-'a'];
		 nums[it->first] = iMask / iMul;
		 iMask %= iMul;
	 }
	
	
 }

 void Init()
 {
	 for (auto& ch : m_target)
	 {
		 m_mTarget[ch]++;
	 }
	 m_iTargetMask = MakeMask(m_mTarget);

	 int iMul = 1;
	 for (auto& it : m_mTarget)
	 {
		 iMul *= (it.second + 1);
	 }
	 for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
	 {
		 iMul /= (it->second + 1);
		 m_vCharMul[it->first - 'a'] = iMul;
	 }
 }

 std::string m_target;
 int m_iTargetMask;
 std::unordered_map<char, int> m_mTarget;
 int m_vCharMul[26] ;

};

2023年1月第4版

class CCTestHash
{
public:
std::size_t operator()(const std::unordered_map<char, int>& nums) const
{
return MakeMask(nums);
}
static int MakeMask(const std::unordered_map<char, int>& nums)
{
int iMask = 0;
for (const auto& mm : m_mTarget)
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && (it->second > 0))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}

static void Init()
 {
	m_mTarget.clear();
	 for (auto& ch : m_target)
	 {
		 m_mTarget[ch]++;
	 }
	 m_iTargetMask = MakeMask(m_mTarget);

	 int iMul = 1;
	 for (auto& it : m_mTarget)
	 {
		 iMul *= (it.second + 1);
	 }
	 for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
	 {
		 iMul /= (it->second + 1);
		 m_vCharMul[it->first - 'a'] = iMul;
	 }
 }

static std::string m_target;
static int m_iTargetMask;
static std::unordered_map<char, int> m_mTarget;
static int m_vCharMul[26];

};
std::string CCTestHash::m_target;
int CCTestHash::m_iTargetMask;
std::unordered_map<char, int> CCTestHash::m_mTarget;
int CCTestHash::m_vCharMul[26];

class Solution {
public:
int minStickers(vector& stickers, string target) {
CCTestHash::m_target = target;
CCTestHash::Init();

	 std::unordered_set<std::unordered_map<char, int>, CCTestHash> hasMask;
	 {			 
		 for (int i = stickers.size() - 1; i >= 0; i--)
		 {
			 std::unordered_map<char, int> mCur;
			 for (auto& ch : stickers[i])
			 {
				 if (m_testHask.m_mTarget.count(ch))
				 {
					 mCur[ch]++;
				 }
			 }
			 if (0 == mCur.size())
			 {
				 continue;
			 }
			 if (hasMask.count(mCur))
			 {
				 continue;
			 }
			 hasMask.insert(mCur);
		 }
	 }
	
	 std::unordered_set<std::unordered_map<char, int>, CCTestHash> setPreMask, setHasDo;
	 setPreMask.insert(CCTestHash::m_mTarget);
	 setHasDo.insert(CCTestHash::m_mTarget);
	 for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
	 {
		 std::unordered_set<std::unordered_map<char, int>, CCTestHash> dp;
		 for (auto& mPre : setPreMask)
		 {
			 char chFristNeedChar = 0;
			 for (auto& it : mPre)
			 {
				 if (it.second > 0)
				 {
					 chFristNeedChar = it.first;
					 break;
				 }
			 }

			 for (auto& mCur : hasMask)
			 {
				 if ((0 == mCur.count(chFristNeedChar)) || (mCur.find(chFristNeedChar)->second <= 0 ))
				 {
					 continue;
				 }

				 auto newMask = GetSubMask(mPre, mCur);
	
				 if (setHasDo.count(newMask))
				 {
					 continue;
				 }
				 if (CCTestHash::MakeMask(newMask) == 0)
				 {
					 return iOpeNum;
				 }
				 setHasDo.insert(newMask);
				 dp.insert(newMask);
			 }
		 }
		 setPreMask.swap(dp);
	 }
	 
	 
	 return -1;
 }
 std::unordered_map<char, int> GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur)
 {
	 std::unordered_map<char, int> vRet;
	 for (auto& pre : mPre)
	 {
		 auto cur = mCur.find(pre.first);
		 if (mCur.end() != cur)
		 {
			 vRet[pre.first] = max(0, pre.second - cur->second);
		 }
		 else
		 {
			 vRet[pre.first] = pre.second;
		 }
	 }
	 return vRet;
 }

 /*
 int MakeMask(const std::unordered_map<char, int>& nums)const
 {
	 int iMask = 0;
	 for (const auto& mm : m_mTarget )
	 {
		 auto it = nums.find(mm.first);
		 if ((nums.end() != it) && ( it->second > 0 ))			
		 {
			 iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
		 }
		 else
		 {
			 iMask = iMask * (mm.second + 1);
		 }
	 }
	 return iMask;
 }
 void ParseMask(std::unordered_map<char, int>& nums, int iMask)
 {
	 for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
	 {
		 const int iMul = m_vCharMul[it->first-'a'];
		 nums[it->first] = iMask / iMul;
		 iMask %= iMul;
	 }
	
	
 }
 */
 CCTestHash m_testHask;

};

【状态压缩】【动态规划】【C++算法】691贴纸拼词,# 算法题,算法,动态规划,c++,LeetCode,状态压缩,贴纸,拼词

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

【状态压缩】【动态规划】【C++算法】691贴纸拼词,# 算法题,算法,动态规划,c++,LeetCode,状态压缩,贴纸,拼词文章来源地址https://www.toymoban.com/news/detail-805831.html

到了这里，关于【状态压缩】【动态规划】【C++算法】691贴纸拼词的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

【状态压缩】【动态规划】【C++算法】691贴纸拼词

作者推荐

本文涉及知识点

LeetCode:691 贴纸拼词

封装类

动态规划

动态规划的状态表示

动态规划的转移方程

动态规划的填表顺序

动态规划的初始状态

动态规划的返回值

代码

核心代码

测试用例

改进简洁版，性能略差

动态规划的状态表示

动态规划的转移方程。

2023年1月第一版

2023年1月第2版

2023年1月第三版

2023年1月第4版

扩展阅读

视频课程

相关下载

测试环境

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

【状态压缩】【动态规划】【C++算法】691贴纸拼词

作者推荐

本文涉及知识点

LeetCode:691 贴纸拼词

封装类

动态规划

动态规划的状态表示

动态规划的转移方程

动态规划的填表顺序

动态规划的初始状态

动态规划的返回值

代码

核心代码

测试用例

改进简洁版，性能略差

动态规划的状态表示

动态规划的转移方程。

2023年1月第一版

2023年1月第2版

2023年1月第三版

2023年1月 第4版

扩展阅读

视频课程

相关下载

测试环境

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

2023年1月第4版