螺旋归纳DP

目录螺旋归纳力扣 LCP 14. 切分数组力扣 3573. 买卖股票的最佳时机 V螺旋归纳数学归纳法中的螺旋归纳参考归纳法。简单的说就是2个dp函数交替求解。力扣 LCP 14. 切分数组给定一个整数数组nums小李想将nums切割成若干个非空子数组使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量请求出最少可以切成多少个子数组。示例 1输入nums [2,3,3,2,3,3]输出2解释最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 第二个子数组头尾数字的最大公约数为 3 。示例 2输入nums [2,3,5,7]输出4解释只有一种可行的切割[2], [3], [5], [7]限制1 nums.length 10^52 nums[i] 10^6递推式数组a的下标是从1到nsplitArray函数是一个数组的最小切分数lcm(k)是数组a前k个数的最小公倍数dp[k]splitArray(a[1...k])即前k个数的最小切分数dp[0]0, dp[1]1f(p,k) min{dp[i] | 0ik,p|a[i1]} , 其中p|lcm(k), f(p,k)表示前k个数中一个p的倍数前面的子数组的最小切分数dp[k] min{f(p,k)1 | p|a[k]}把形如f(......k)的所有式子打包到一起看成一个整体g(k)。那么g(k)的求解依赖dp(0)到dp(k-1)这k项而dp(k)的求解依赖g(k)所以整体是一个螺旋归纳法。具体实现实际上lcm也是一个动态规划的函数是数列的一维动态规划。也就是说整体是3个动态规划函数的螺旋归纳。在实现层面还需要降维把f降到1维把lcm降到0维。代码为了方便对照写了个形式最贴近递推式的代码class Solution { public: int dp(int k) { if (k 2)return k; if (m_dp[k])return m_dp[k]; vectorint v GetFacs(nums[k]); g(v, k); int ans INT_MAX; for (auto vi : v) ans min(ans, f(vi, k) 1); return m_dp[k]ans; } void g(vectorintv,int k) { for (auto vi : v) { if (m_f.find(vi) m_f.end())m_f[vi] dp(k - 1); else m_f[vi] min(m_f[vi], dp(k - 1)); } } int f(int p, int k) { return m_f[p]; } int splitArray(vectorint nums) { this-nums nums; nums.insert(nums.begin(), 0); return dp(nums.size() - 1); } vectorint nums; mapint, intm_f; mapint, intm_dp; };可惜代码是错的。改正之后class Solution { public: int dp(int k) { if (k 1)return 0; if (m_dp[k])return m_dp[k]; vectorint v GetFacs(nums[k]); g(v, k); int ans INT_MAX; for (auto vi : v) ans min(ans, f(vi, k) 1); return m_dp[k]ans; } void g(vectorintv,int k) { for (auto vi : v) { int ans dp(k - 1); if (m_f.find(vi) m_f.end())m_f[vi] ans; else m_f[vi] min(m_f[vi], ans); } } int f(int p, int k) { return m_f[p]; } int splitArray(vectorint nums) { this-nums nums; this-nums.insert(this-nums.begin(), 0); auto x dp(this-nums.size() - 1); return x; } vectorint nums; mapint, intm_f; mapint, intm_dp; };改的很微妙可能只有螺旋归纳才会出现这种现象。逻辑对了但是在极限用例下会超时。把代码化简顺便做个性能优化class Solution { public: int dp(int k) { if (k 1)return 0; vectorint v GetFacs(nums[k]); for (auto vi : v) { int ans m_dp[k - 1]; if (m_f.find(vi) m_f.end())m_f[vi] ans; else m_f[vi] min(m_f[vi], ans); } int ans INT_MAX; for (auto vi : v) ans min(ans, m_f[vi] 1); return m_dp[k]ans; } int splitArray(vectorint nums) { this-nums nums; this-nums.insert(this-nums.begin(), 0); for (int i 1; i this-nums.size(); i)dp(i); return m_dp[this-nums.size() - 1]; } vectorint nums; mapint, intm_f; mapint, intm_dp; };这样就不出意外的AC了。力扣 3573. 买卖股票的最佳时机 V给你一个整数数组prices其中prices[i]是第i天股票的价格美元以及一个整数k。你最多可以进行k笔交易每笔交易可以是以下任一类型普通交易在第i天买入然后在之后的第j天卖出其中i j。你的利润是prices[j] - prices[i]。做空交易在第i天卖出然后在之后的第j天买回其中i j。你的利润是prices[i] - prices[j]。注意你必须在开始下一笔交易之前完成当前交易。此外你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。通过进行最多k笔交易返回你可以获得的最大总利润。示例 1:输入:prices [1,7,9,8,2], k 2输出:14解释:我们可以通过 2 笔交易获得 14 美元的利润一笔普通交易第 0 天以 1 美元买入第 2 天以 9 美元卖出。一笔做空交易第 3 天以 8 美元卖出第 4 天以 2 美元买回。示例 2:输入:prices [12,16,19,19,8,1,19,13,9], k 3输出:36解释:我们可以通过 3 笔交易获得 36 美元的利润一笔普通交易第 0 天以 12 美元买入第 2 天以 19 美元卖出。一笔做空交易第 3 天以 19 美元卖出第 4 天以 8 美元买回。一笔普通交易第 5 天以 1 美元买入第 6 天以 19 美元卖出。提示:2 prices.length 1031 prices[i] 1091 k prices.length / 2思路螺旋归纳首先按照单调性做区间分割然后定义2个函数dp表示前vpId1段折线内产生最多n次交易的最大收益dp2表示以vpId为结尾的产生最多n次交易的最大收益那么dp的递推式就是分为2种情况即是否以vpId为结尾而dp2的递推式就是分为3种情况:1vpId-1没有被采用即vpId就是交易起点2vpId-1有被采用vpId不是交易起点那么vpId-1也不是交易起点即算上vpId之后至少是3段单调段连起来的交易而且肯定是奇数段3vpId-1有被采用vpId是交易起点即交易类型反转普通和做空的反转class Solution { public: long long maximumProfit(vectorint prices, int k) { this-prices prices; this-vp getBrokenLine(prices); m.clear(); m2.clear(); auto ans dp(vp.size() - 1, k); return ans; } //前vpId1段折线内产生最多n次交易的最大收益 long long dp(int vpId, int n) { if (vpId 0)return 0; if (m[vpId].find(n) ! m[vpId].end()) { return m[vpId][n]; } return m[vpId][n] max(dp(vpId - 1, n), dp2(vpId, n)); } //以vpId为结尾的产生最多n次交易的最大收益 long long dp2(int vpId, int n) { if (vpId 0)return 0; if (vpId 0)return n 0 ? 0 : abs(prices[vp[vpId].second] - prices[vp[vpId].first]); if (n 0)return 0; if (m2[vpId].find(n) ! m2[vpId].end()) { return m2[vpId][n]; } long long ans dp(vpId - 2, n - 1) abs(prices[vp[vpId].second] - prices[vp[vpId].first]); if(vpId1)ans max(ans, dp2(vpId - 2, n) getFlag(vpId) * (prices[vp[vpId].second] - prices[vp[vpId-2].second])); if (vpId 0)ans max(ans, dp2(vpId - 1, n - 1) abs(prices[vp[vpId].second] - prices[vp[vpId].first]) - g(vp[vpId].first)); return m2[vpId][n] ans; } long long getFlag(int vpId) { if (prices[vp[vpId].second] prices[vp[vpId].first])return 1; return -1; } long long g(int id) { return min(abs(prices[id] - prices[id 1]), abs(prices[id] - prices[id - 1])); } vectorint prices; vectorpairint, int vp; unordered_mapint, unordered_mapint, long longm; unordered_mapint, unordered_mapint, long longm2; };