jetbrains 二叉树排序 双重检验锁 阿里云 人工智能 swift oauth yii2 swift2 Component vue全局组件 后台模板下载 河南省普通话考试官网 ai视频教程下载 android项目开发 jquery获取元素 bootstrap日历插件 时间戳java 查看nodejs版本 ubuntu显示隐藏文件夹 html下拉框默认选中 xshell搭建ss Navicat python最大值 java连接mysql java中scanner java开发环境配置 java的运行环境 java字符串替换 java环境包 javaenum linux系统安装 广告代码 js删除数组指定元素 图片放大软件 矩阵分析与应用 视频修复工具 狮子狗皮肤 js字符转数字 ppt格式刷怎么用
当前位置: 首页 > 学习教程  > 编程语言

yp集之p6DP核心和细节

2021/1/13 20:45:57 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

文章目录:概念:经典样例:数字三角形:最长公共子序列问题 (LCS问题)参考概念: 局部最优达到全局最优,与分治最大区别在于分治分解的子问题没有联系,可以说是dp是分治的子…

文章目录:

  • 概念:
  • 经典样例:
    • 数字三角形:
    • 最长公共子序列问题 (LCS问题)
      • 参考

概念:

局部最优达到全局最优,与分治最大区别在于分治分解的子问题没有联系,可以说是dp是分治的子结构重复的优化,分治法做dp题花销太大,没有联系就分治
贪心区别:贪心决策不可撤回式决策,每次局部最优,当前决策不依赖以前决策也不将影响将来的决策,而dp,是利用与此决策步骤有关的以前dp好的子问题子分支选择最好的,与此步骤的值共同构建此节点dp,可以说,贪心,不顾头不顾尾巴,活在当下,而dp瞻前顾后,完美选择。

经典样例:

数字三角形:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

#include<bits/stdc++.h>
using namespace std;
#define MAX 100
int D[MAX][MAX];
int n;

int maxsum(int i,int j){
   if(i==n) return D[i][j];
   int x=maxsum(i+1,j);
   int y=maxsum(i+1,j+1);
   return max(x,y)+D[i][j];
}

int main(){
   cin>>n;
   for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
        cin>>D[i][j];
   cout<<maxsum(1,1)<<endl;
   system("pause");
}

结果:30
重复计算:
在这里插入图片描述
记忆化:

在这里插入代码片#include<bits/stdc++.h>
using namespace std;
#define MAX 100
int D[MAX][MAX];
int maxSum[MAX][MAX];
int n;

int maxsum(int i,int j){
   if(maxSum[i][j]!=-1) return maxSum[i][j];
   if(i==n) return maxSum[i][j]=D[i][j];
   int x=maxsum(i+1,j);
   int y=maxsum(i+1,j+1);
   return max(x,y)+D[i][j];
}

int main(){
   cin>>n;
   for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++){
         cin>>D[i][j];
         maxSum[i][j]=-1;
      }
   cout<<maxsum(1,1)<<endl;
   system("pause");
}

递归转递推:

#include<bits/stdc++.h>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n; int *maxSum;
int main(){
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
       for(j=1;j<=i;j++) 
          cin>>D[i][j];

    maxSum=D[n];//maxSum指向第N行
    for(int i=n-1;i>=1;--i)
       for(int j=1;j<=i;++j)
          maxSum[j]=max(maxSum[j],maxSum[j+1])+D[i][j];
    cout<<maxSum[1]<<endl;
    system("pause");
}

首先递归应该是我们解决动态规划问题最常用的方法,帅,速度不算太慢
过程:
1、将原问题分解为子问题
2、确定状态
3、确定一些初始状态(边界条件)的值
4、确定状态转移方程

最长公共子序列问题 (LCS问题)

给你两个序列,问你他们的最长LCS序列的长度是多少?(序列可以是不连续的,只要元素的相对位置一
样)(不了解LCS问题的自行百度)
那么在LCS问题中dp的思想体现在哪里呢?

重复子问题:(超级容易发现的一个)

我们要求x1xi,Y1Yj的LCS,那么是不是要求x1xi-1,Y1Yi-1的LCS

我们要求x1xi-1,y1yi-1的LCS,那么是不是要求x1xi-2,Y1yi-2的LCS

所以我们要求的x1xi,Y1Yj的LCS这个大问题中,包含了很多的重复子问题
具体做法:

c【i】【j】表示x1xi,Y1Yj的LCS序列长度

x【i】==y【j】 c【i】【j】=c【i-1】【j-1】+1

x【i】!=y【j】 c【i】【j】=max(c【i-1】【j】,c【i】【j-1)

i0||j0 c【i】【j】=0

贴个代码(求最优值和最优解)

#include<bits/stdc++.h>
#define max_v 1005
using namespace std;
char x[max_v],y[max_v];
int dp[max_v][max_v];
int l1,l2;
int dfs(int i,int j)
{
    if(i==-1||j==-1)
        return 0 ;
    if(x[i]==y[j])//来自左上角
    {
        dfs(i-1,j-1);
        cout<<x[i]<<" ";//先递归到最后再输出,,这样就是顺序的
    }
    else
    {
        if(dp[i-1][j]>dp[i][j-1])//来自上面
        {
            dfs(i-1,j);
        }
        else//来自左边
        {
            dfs(i,j-1);
        }
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        scanf("%s",x);
        scanf("%s",y);
        int l1=strlen(x);
        int l2=strlen(y);
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=l1; i++)
        {
            for(int j=1; j<=l2; j++)
            {
                if(x[i-1]==y[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        printf("%d\n",dp[l1][l2]);
        dfs(l1,l2);
        cout<<endl;
    }
    return 0;
}

参考

链接: ( DP思想.).
链接: ACM总结.
链接: 数位DP.
链接: bilibili.
链接: 背包九讲思维.
链接: 背包九讲代码.
链接: 人话版.


本文链接: http://www.dtmao.cc/news_show_600447.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?