动态规划状态转移公式

最大连续子序列和

转移情况：
①最大和的连续序列只有一个元素，即A[i]本身，为A[i]
②最大和的连续序列有多个元素，即从A[j]开始到A[i]，为dp[i-1]+A[i]

int maxSub(int n){
int Max=0;
for(int i=0;i<n;i++){
if(i==0) dp[i]=a[i];//初始
else dp[i]=max(dp[i-1]+a[i],a[i]);//多个vs一个
if(dp[i]>Max) Max=dp[i];
}
return Max;
}

最长递增子序列

转移情况：
①A[i]之前的元素都比A[i]大，即最长递增子序列只有A[i]本身，为dp[i]=1
②A[i]之前的元素A[j]比A[i]小此时只需将A[i]添加到以A[j]为末尾的最长递增子序列,而求长度则是通过将i之前的元素逐一遍历，就可以获得dp[i]

int answer=0;
for(int i=0;i<n;i++){
dp[i]=1;//初始化为1
for(int j=0;j<i;j++){//得出以i为最后一个的最大的序列长度
if(height[i]<=height[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
answer=max(answer,dp[i]);
}

最长公共子序列

转移情况：
①s1[i]=s2[j]，此时比存在一个最长公共子序列以s1[i]和s2[j]结尾，其他部分相当于s1的前i-1和s2的前j-1个字符的最长公共子序列，为dp[i-1][j-1]+1
②s1[i]!=s2[j],此时最长公共子序列的长度为s1的前i-1个字符和s2的前j个字符的最长公共子序列与s1的前i个字符和s2中的前j-1个字符的最长公共子串的较大者，为max(dp[i-1][j],dp[i][j-1])

边界情况：
dp[i][0]=0; dp[0][j]=0;

while(scanf("%s%s",s1+1,s2+1)!=EOF){//从下标1开始输入
int n=strlen(s1+1);
int m=strlen(s2+1);
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0||j==0){//边界条件初始化
dp[i][j]=0;
continue;
}
//状态转移方程
if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[n][m]<<endl;
}

背包问题

• 0-1背包

转移情况：
①对于容量为j的背包，如果不放入第i件物品，问题就转化成了前i-1个物品放入容量为j的背包的问题，为dp[i-1][j]
②对于容量为j的背包，如果放入第i件物品，问题就转化成了将前面i-1个物品放入容量为j-w[i]的背包的问题，为dp[i-1][j-w[i]]+v[i]
最终转化成了dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
经观察dp[i][j]只与二维数组中本行的上一行有关，根据这个可以将二维数组优化为一维数组：
dp[j]=max(dp[j],dp[j-w[i]+v[i])

边界情况：
dp[i][0]=0; dp[0][j]=0;

for(int i=0;i<=m;i++){
dp[i]=0;//初始化
}
for(int i=0;i<n;i++){
for(int j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}

• 完全背包 ：暂时不是很理解(╯°Д°)╯︵┻━┻
• 多重背包 ：暂时不是很理解ヽ(｀Д´)ﾉ︵ ┻━┻ ┻━┻

最后

以上就是甜美猫咪为你收集整理的动态规划状态转移公式的全部内容，希望文章能够帮你解决动态规划状态转移公式所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。