20210715动态规划练习
多思考，多练习自己的逻辑思维能力。
数组分组问题
题意：
一个数组可被分为n组，整个数组的权值被定义为各组内数字之积对1000取模后的总和，求数组的最大权值
借鉴他人思路：
用dp[i]存放前i个元素的最大权值。j表示倒数第二个分组的最后一个元素的索引。则前i个元素的的最大权值为：前j个元素的最大权值加上j+1至i元素组成的数组的权值之和。但是由于j的值不确定，因此要在0与i之间搜索。核心代码：dp[i]=max(dp[i],dp[j]+dp[j+1][i]
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e3+100,mod=5;
int n,a[maxn];
int dp[maxn];//用来存放当前i个分组的最大值
int pre[maxn][maxn];//用来预处理每个区间的乘积
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
pre[i][i]=a[i];//第i行从第i个元素开始
for(int j=i+1;j<=n;j++){
pre[i][j]=(pre[i][j-1]*a[j])%mod;
}
}
dp[1]=a[1];
for(int i=2;i<=n;i++){
for(int j=0;j<i;j++){
dp[i]=max(dp[i],dp[j]+pre[j+1][i]);
}
}
printf("%d",dp[n]);
return 0;
}
巧妙之处：
1、用pre[i][j]数组存放第i至第j元素组成数组的权值
2、在计算d[i]之前进行预处理，对权值取模，简便运算
3、动态规划寻找j+1与i之间的最大权值
Leecode416数组等和分割问题
题意：
给你一个仅包含正整数的非空数组，请判断是否可以将这个数组分割成两个子集使者两个子集中的元素和相等。
思路：
类似于背包问题，选取适当的元素使其元素值之和等于元素和的一半。因此可模仿背包问题求解。仔细考虑此问题，有两种特殊情况可以进行剪枝。
- 当数组所有元素之和为奇数时，怎样也不可能平均分割，直接返回
- 当数组中最大的元素大于数组之和的一半时，也不可能完成平均分割，直接返回
采用动态规划的解法重要两个步骤：
第一步：确定状态的表示。
创建二维数组dp[i][j]表示能否在前i个元素中找出值之和为j的情况。
第二步：确定状态转移方程。
在确定好状态表示之后需要考虑状态的边界情况。
边界一：显然在元素和j为0的条件下，前任意个元素中都能找到满足此条件的情况。即：dp[i][0]=true;
边界二：显然在前0个元素中仅有一种元素和为nums[0]的情况，即：if(i==nums[0]) dp[0][i]=true; else dp[0][i]=false;
状态考虑：
当第i个元素nums[i]大于当前所遍历的和值j时，为了保证前i个元素值之和等于j，那么第i个元素肯定不能取。状态转换关系只能是dp[i][j]=dp[i-1][j];
当第i个元素nums[j]小于等于j时，那么第i个元素可取可不取。状态转换为：
dp[i][j]=dp[i-1][j]|dp[i-1][j-nums];
综上：状态转移方程为：
核心代码
bool canPartition(int* nums, int numsSize){
int sum=0,maxNum=0;
bool dp[200][20000];//前i个元素是否有可以挑选出之和等于j的可能
for(int i=0;i<numsSize;i++){
sum+=nums[i];
if( maxNum<nums[i])
maxNum=nums[i];
}
if(sum%2!=0)
return false;
if(sum/2<maxNum)
return false;
for(int i=0;i<numsSize;i++)
{
dp[i][0]=true;
dp[0][i]=false;
}
dp[0][nums[0]]=true;
for(int i=1;i<numsSize;i++)
for(int j=1;j<=sum/2;j++){
if(nums[i]>=j)
dp[i][j]=dp[i-1][j];
else dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[i]];
}
return dp[numsSize-1][sum/2];
}
巧妙之处：
1、状态的表示方法：dp[i][j]
2、含0边界的确定是最容易出错的。
for(int i=0;i<numsSize;i++)
{
dp[i][0]=true;
dp[0][i]=false;
}
dp[0][nums[0]]=true;
Leecode494目标和问题
题意：
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目
思路：今天鸽子了，明天补上。