作者推荐
【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠
本文涉及知识点
动态规划汇总
LeetCode:2518. 好分区的数目
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。
如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
示例 1：
输入：nums = [1,2,3,4], k = 4
输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
示例 2：
输入：nums = [3,3,3], k = 4
输出：0
解释：数组中不存在好分区。
示例 3：
输入：nums = [6,6], k = 2
输出：2
解释：可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。
参数范围：
1 <= nums.length, k <= 1000
1 <= nums[i] <= 109
动态规划
动态规划的状态表示
暴力做法：dp[i][j][m] 记录前i个 数子，第一个分区和为j，第二个分区和为m。这样时间复杂度O(109)超时。
状态优化
j+m 显然等于y= ∑ x : 0 i − 1 \Large\sum_{x:0}^{i-1} ∑x:0i−1nums[x]
{ 第一个分区和为 p r e , 第二个分区和为 j − p r e p r e < k 第一个分区和大于等于 k ，第二个分区和 p r e − k p r e ∈ [ k , 2 k ] \begin{cases} 第一个分区和为pre,第二个分区和为j-pre & pre<k \\ 第一个分区和大于等于k，第二个分区和pre-k & pre\in[k,2k] \end{cases} {第一个分区和为pre,第二个分区和为j−pre第一个分区和大于等于k，第二个分区和pre−kpre<kpre∈[k,2k]
pre[j]表示前i个数的形成的分区数量,dp[j]表示前i+1个数。
状态数：O(k nums.length)
动态规划的转移方程
分两种情况：nums[i] 属于分区一，属于分区二。
转移方程时间复杂度：O(1)。
总时间复杂度：O(k nums.length)
动态规划的初始值
pre[0]=1，其它等于0。
动态规划的填表顺序
i从0到大，前者状态更新后置状态。
动态规划的返回值
pre.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;
}
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 countPartitions(vector<int>& nums, int k) {
vector<C1097Int<>> vPre(2 * k + 1);
vPre[0] = 1;
long long llSum = 0;
for (const auto& n : nums)
{
vector<C1097Int<>> dp(2 * k + 1);
for (int pre = 0; pre <= 2 * k; pre++)
{
const long long sum1 = (pre < k) ? pre : k;
const long long sum2 = min((long long)k,((pre < k) ? (llSum - pre) : (pre - k)));
//分区一
const long long sum11 = min((long long)k, sum1 + n);
const long long sum22 = min((long long)k, sum2 + n);
auto Updata = [&dp,&vPre, &pre,&k] (long long sum1, long long sum2)
{
if (sum1 < k)
{
dp[sum1] += vPre[pre];
}
else
{
dp[k+sum2] += vPre[pre];
}
};
Updata(sum11, sum2);
Updata(sum1, sum22);
}
vPre.swap(dp);
llSum += n;
}
return vPre.back().ToInt();
}
};
测试用例
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<int> nums;
int k;
{
Solution sln;
nums = { 1, 2, 3, 4 }, k = 4;
auto res = sln.countPartitions(nums, k);
Assert(res,6);
}
{
Solution sln;
nums = { 3, 3, 3 }, k = 4;
auto res = sln.countPartitions(nums, k);
Assert(res, 0);
}
{
Solution sln;
nums = { 6,6 }, k = 2;
auto res = sln.countPartitions(nums, k);
Assert(res, 2);
}
}
2023年2月
class C1097Int
{
public:
C1097Int(int iData = 0) :m_iData(iData)
{
}
C1097Int operator+(const C1097Int& o)const
{
return C1097Int(((long long)m_iData + o.m_iData) % s_iMod);
}
C1097Int& operator+=(const C1097Int& o)
{
m_iData = ((long long)m_iData + o.m_iData) % s_iMod;
return *this;
}
C1097Int& operator-=(const C1097Int& o)
{
m_iData = (m_iData + s_iMod - o.m_iData) % s_iMod;
return *this;
}
C1097Int operator*(const C1097Int& o)const
{
return((long long)m_iData *o.m_iData) % s_iMod;
}
C1097Int& operator*=(const C1097Int& o)
{
m_iData =((long long)m_iData *o.m_iData) % s_iMod;
return *this;
}
bool operator<(const C1097Int& o)const
{
return m_iData < o.m_iData;
}
C1097Int& pow( int n)const
{
C1097Int iRet = 1, iCur = *this;
while (n)
{
if (n & 1)
{
iRet *= iCur;
}
iCur *= iCur;
n >>= 1;
}
return iRet;
}
C1097Int PowNegative1()
{
return pow(s_iMod - 2);
}
int ToInt()const
{
return m_iData;
}
private:
int m_iData = 0;;
static const int s_iMod = 1000000007;
};
int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}
int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}
int operator*(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator*(C1097Int(iData)).ToInt();
return iRet;
}
int& operator*=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator*(C1097Int(iData)).ToInt();
return iData;
}
class Solution {
public:
int countPartitions(vector& nums, int K) {
//pre0 记录选取的数组和低于k，pre1 记录选取的数组和超过k，未选取的数组和低于k
vector pre0(K), pre1(K);
pre0[0] = 1;
C1097Int iRet;
long long llSum = 0;
for (const auto& n : nums)
{
llSum += n;
vector dp0 = pre0, dp1 = pre1;
iRet += iRet;//已经符合要求的，选取不选取都符合
//选取
for (int pr = 0; pr < K; pr++)
{
const int iSelSum = pr + n;
const auto& preValue = pre0[pr];
if (0 == preValue.ToInt())
{
continue;
}
if (iSelSum< K)
{
dp0[iSelSum] += preValue;
}
else
{
const long long llNoSelSum = llSum - iSelSum;
if (llNoSelSum >= K)
{
iRet += preValue;
}
else
{
dp1[llNoSelSum] += preValue;
}
}
}
//不选取
for (int pr = 0; pr < K; pr++)
{
const int iNoSelSum = pr + n;
const auto& preValue = pre1[pr];
if (0 == preValue.ToInt())
{
continue;
}
if (iNoSelSum < K)
{
dp1[iNoSelSum] += preValue;
}
else
{
iRet += preValue;
}
}
pre0.swap(dp0);
pre1.swap(dp1);
}
return iRet.ToInt();
}
};
