网站图片特效源码,外贸网站建设服务商,广州保安公司注册,塘厦水霖学校动态规划解题步骤#xff1a;
1.确定状态表示#xff1a;dp[i]是什么
2.确定状态转移方程#xff1a;dp[i]等于什么
3.初始化#xff1a;确保状态转移方程不越界
4.确定填表顺序#xff1a;根据状态转移方程即可确定填表顺序
5.确定返回值
题目链接#xff1a;446.…动态规划解题步骤
1.确定状态表示dp[i]是什么
2.确定状态转移方程dp[i]等于什么
3.初始化确保状态转移方程不越界
4.确定填表顺序根据状态转移方程即可确定填表顺序
5.确定返回值
题目链接446. 等差数列划分 II - 子序列 - 力扣LeetCode 题解1三层for循环
1.状态表示dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数
2.状态转移方程difnums[j]-nums[i] 如果存在nums[k]nums[i]-dif 0ki 可能存在多个nums[k]每个都要算 dp[i][j]dp[k][i]1
3.初始化创建dp表时全部初始化为0
4.填表顺序从上往下从左往右哦依次填写二维dp表
5.返回值返回dp表中所有元素之和理论上是上三角部分但是由于下三角和对角线都为0因此返回总和也没问题
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {//dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数//difnums[j]-nums[i]//nums[k]nums[i]-dif//如果存在nums[k] 0ki//重复的nums[k]也算//dp[i][j]dp[k][i]1size_t nnums.size();//创建dp表vectorvectorint dp(n,vectorint(n,0));//初始化//创建dp表时全部初始化为0//填表for(int j2;jn;j){for(int i1;ij;i){long long dif(long long)nums[j]-nums[i];long long tempnums[i]-dif;for(int k0;ki;k){if(nums[k]temp){ dp[i][j]dp[k][i]1;}}}}//返回值返回dp表之和2处理为0int ans0;for(auto row:dp){for(auto value:row){ansvalue;}}return ans;}};
题解2使用hash表代替一层for循环
在填dp表之前先将所有nums值和其对应的下标填入hash表对于重复的nums值存在多个下标使用vector存储其下标。查找nums[k]时使用hash表查找hash[nums[k]]返回存储下标的vector再遍历一次vector得到所有的k但是只有满足小于i的k才符合条件。
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {//dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数//difnums[j]-nums[i]//nums[k]nums[i]-dif//如果存在nums[k] 0ki//重复的nums[k]也算//dp[i][j]dp[k][i]1size_t nnums.size();//创建hash表nums值和下标绑定//重复元素有多个下标则使用数组存储unordered_maplong long,vectorint hash;for(int i0;in;i){hash[nums[i]].push_back(i);}//创建dp表vectorvectorint dp(n,vectorint(n,0));//初始化//创建dp表时全部初始化为0//填表for(int j2;jn;j){for(int i1;ij;i){long long dif(long long)nums[j]-nums[i];long long tempnums[i]-dif;if(hash.count(temp)){for(auto k:hash[temp]){if(ki)dp[i][j]dp[k][i]1;}}}}//返回值返回dp表之和2处理为0int ans0;for(auto row:dp){for(auto value:row){ansvalue;}}return ans;}};
