专栏首页ACM算法日常最佳加法表达式 DP

最佳加法表达式 DP

题意:

有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少。 输入: 5 3 1 2 3 4 5 输出: 24

核心内容总结:所谓的DP是指 从最小的子结构最优,推往全局的过程。

跟是不是递推或者dfs还是记忆化无半毛钱关系。

重剑无锋大巧不工,贵在领悟精神。

今天写这篇主要是为了总体的认识一下DP。

DP是什么呢:说白了就是一个找最优子结构的过程,至于愿怎么找,那就随意了。

但说白了核心还是通过遍历(暴力,怎么暴力怎么来)来找各个最优子结构,由最小的局部最优推至全局。

其实拿for循环,循环套循环和dfs都一样,其实都是从最局部最小的问题最优,推至全局最优。

综上总结:1.递推(自底向上法) 2.递归(带备忘的自顶向下法) 其实都是一种东东。

这道题比较典型,就拿这道题为例吧!

在10个数字中放任意个加号使得组成的表达式的和最小。

状态转移方程:

将m个加号插入到n个数字组成的数字串中

V(m,n) 表示将m个加号插入到n个数字组成的数字串中组成的表达式和最小的表达式

i表示在第i个数后面插入加号

V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1)

表达式的最后一个加号添加在第 i 个数字后面

这个i要试遍所有的情况

1.先写一下裸跑dfs,由于不用记忆化,新手的话比较容易理解。

坏处是不开记忆化单纯费时间,因为暴搜的过程中产生了许多冗余的搜索。

好处是不开的话,省下了记忆各个最优子结构的内存。

具体取舍,开还是不开根据实际情况来定。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 99999999;
int a[1005],num[1005][1005];
int V(int m,int n)
{
    if(m == 0)//无加号
        return num[1][n];
    else if(n < m+1)//加号过多
        return INF;
    else
    {
        int t = INF;
        //这里有点像回溯,回溯的话递归里面有循环
        //说说实话,递归真的很简单,就是把递推公式写进来
        for(int i = m;i <= n-1;i++) //这里是n减一,排除了最后一个数字后面放加号的情况
           t = min(t, V(m-1,i)+num[i+1][n]);
        //不懂的位置画个实例,会很简单,因为熟悉,所以容易
        return t;
    }
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1;i <= n;i++)
            scanf("%d",&a[i]);
        //预处理,计算i到j数字串组成的数字
        for(int i = 1;i <= n;i++)
        {
            num[i][i] = a[i];//只有一个数字
            for(int j = i+1;j <= n;j++)
            {
                //这个表达式也可以好好看一下
                num[i][j] = num[i][j-1]*10 + a[j];
            }
        }
        cout<< V(m,n) <<endl;
    }
    return 0;
}

2.记忆化搜索

int V(int m,int n) {
   if(v[m][n]!=0)return v[m][n];
   for(int i = m;i <= n-1;i++)
      t = min(t, V(m-1,i)+num[i+1][n]);
   return v[m][n]=t;
}
既然已经知道当前子结构的最优情况,爆破再遇见时就不用再扫一遍了。
所以因为少扫了很多东西,所以很省时间。
但也得开内存去存各个子结构的最优情况!!!
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 99999999;
int a[1005],num[1005][1005];
int v[1005][1005];
int V(int m,int n)
{
    int t = INF;
    if(v[m][n]!=0)return v[m][n];
    if(m == 0)//无加号
        return num[1][n];
    else if(n < m+1)//加号过多
        return INF;
    else
    {
        //这里有点像回溯,回溯的话递归里面有循环
        //说说实话,递归真的很简单,就是把递推公式写进来
        for(int i = m;i <= n-1;i++) //这里是n减一,排除了最后一个数字后面放加号的情况
           t = min(t, V(m-1,i)+num[i+1][n]);
        //不懂的位置画个实例,会很简单,因为熟悉,所以容易
    }
    return v[m][n]=t;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1;i <= n;i++)
            scanf("%d",&a[i]);
        //预处理,计算i到j数字串组成的数字
        for(int i = 1;i <= n;i++)
        {
            num[i][i] = a[i];//只有一个数字
            for(int j = i+1;j <= n;j++)
            {
                //这个表达式也可以好好看一下
                num[i][j] = num[i][j-1]*10 + a[j];
            }
        }
        cout<< V(m,n) <<endl;
    }
    return 0;
}

3.自下而上的递推 也就是一般而言的DP

留意一下,确实是 i=1,j=i,k=i开始扫的
利用for循环遍历所有情况,而且是自底向上,通过最小单位的子结构 来推往全局的。
for(int i=1;i<=m;i++)
    for(int j=i;j<=n;j++)
        for(int k=i;k<=j;k++)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1005;
int a[N],num[N][N],dp[N][N];
//a[N]里面是存数字串
//num[i][j]表示数字串a[N]的第i位到第j位之间的数字串表示的数组
//dp[i][j]在i个数字中插入j个加号所能形成的表达式最小值
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        //预处理,计算i到j数字串组成的数字
        for(int i=1;i<=n;i++){
            num[i][i]=a[i];//只有一个数字
            for(int j=i+1;j<=n;j++){
                num[i][j]=num[i][j-1]*10+a[j];
            }
        }
        memset(dp,0x3f,sizeof(dp));
        for(int i=1;i<=n;i++){
            dp[0][i]=num[1][i];//无加号时
        }
        //其实就是感觉在那个位置放不放加号
        //这里n可以写在m前面。要加一个限制条件n>m,好麻烦,所以m在前且n=m+1
        //这里k的取值范围就是m到n,k表示在第k个数后面插入加号
        for(int i=1;i<=m;i++)
            for(int j=i;j<=n;j++)
                for(int k=i;k<=j;k++)
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+num[k+1][j]);
        cout<<dp[m][n]<<endl;
    }
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:mxg

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • HDU6370:Werewolf 推理+拓扑排序 2018第六场杭电多校

    "The Werewolves" is a popular card game among young people.In the basic game, th...

    ACM算法日常
  • 51nod 1649 齐头并进(Codeforces 601A The Two Routes) (最短路)

    题目链接(Codeforces):http://codeforces.com/problemset/problem/601/A

    Ch_Zaqdt
  • HPU personal-training 2

    A - Kefa and Park 题意:就是一棵树,然后本人的家在根上,餐厅在叶子节点上。然后在前往叶子结点的餐厅的时候,途中的结点上有猫,而这个人特别怕...

    用户7727433
  • 1045 快速排序 (25 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • PAT 1004 Counting Leaves

    1004. Counting Leaves (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

    ShenduCC
  • AIM Tech Round 5 B. Unnatural Conditions(思维)

    题目链接:http://codeforces.com/contest/1028/problem/B

    Ch_Zaqdt
  • BZOJ2655: calc(dp 拉格朗日插值)

    设\(f[i][j]\)表示选了\(i\)个严格递增的数最大的数为\(j\)的方案数

    attack
  • HDU4418 Time travel(期望dp 高斯消元)

    \(f[x] = \sum_{i = 1}^n f[to(x + i)] * p[i] + ave\)

    attack

扫码关注云+社区

领取腾讯云代金券