精华内容
下载资源
问答
  • 动态规划经典题

    2011-12-22 17:09:11
    里面是动态规划算法的经典习题,对动态规划算法的掌握有一定的帮助
  • 动态规划 经典题

    2020-09-25 21:50:53
    (dp )hdu1506 Largest Rectangle in a Histogram ...题目大意:所描绘的直方图的最大对齐矩形 思路:解题要点在于对每个店进行左右延伸,向左延伸的条件是:左边的矩形高度比当前高度高(右边同理),即a[l[i]-1]>...

    (dp )hdu1506 Largest Rectangle in a Histogram

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1506
    题目大意:所描绘的直方图的最大对齐矩形
    思路:解题要点在于对每个店进行左右延伸,向左延伸的条件是:左边的矩形高度比当前高度高(右边同理),即a[l[i]-1]>a[i],初始设l[i]=i,r[i]=i;即还未延伸状态,初始当前点的宽度为r[i]-l[i]+1=1;
    AC代码如下:

    #include <iostream>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    typedef long long ll;
    #define M 100000+5
    ll a[M];
    int n;
    ll l[M],r[M];
    int main()
    {
        while(cin >>n&&n)
        {
            for(int i=1;i<=n;i++)
              cin >>a[i];
            a[0]=-1;
            a[n+1]=-1;//该直方图的两侧的高度设为一个很小值,防止延伸时出现死循环
            l[0]=1;
            r[n+1]=n;
            for(int i=1;i<=n;i++)
            {
                l[i]=i;
                while(a[l[i]-1]>=a[i])
                    l[i]=l[l[i]-1];
                //cout <<i<<" "<<l[i]<<endl;
            }
            for(int i=n;i>=1;i--)
            {
                r[i]=i;
                while(a[r[i]+1]>=a[i])
                    r[i]=r[r[i]+1];
                //cout <<i<<" "<<r[i]<<endl;
            }
            ll maxx=-1;
            for(int i=1;i<=n;i++)
              maxx=max(a[i]*(r[i]-l[i]+1),maxx);
            cout <<maxx<<endl;
        }
        return 0;
    }
    

    (dp )hdu1505 City Game

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1505
    题目大意:求给出矩阵块中最大的全部为F的子矩阵
    思路:遍历每行的点,若当前点为‘F’,则a[i][j]=a[i-1][j]+1,代表该列的上面的能达到的最高长度,后面处理与上面的hdu1506类似,再考虑往左右延伸能达到的最大宽度
    AC代码:

    #include <iostream>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    
    #define M 1000+5
    int a[M][M];
    int l[M][M],r[M][M];
    char c;
    int main()
    {
        int k,m,n;
        cin >>k;
        while(k--)
        {
            cin >> m>> n;
            memset(a,0,sizeof(a));
            memset(l,0,sizeof(r));
            memset(r,0,sizeof(r));
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    cin >> c;
                    if(c=='F')
                        a[i][j]=a[i-1][j]+1;
                }
            }
            int maxx=-1;
            for(int i=1;i<=m;i++)
            {
                l[i][0]=1;
                l[i][n+1]=n;
                a[i][0]=-1;
                a[i][n+1]=-1;
                for(int j=1;j<=n;j++)
                {
                    l[i][j]=j;
                    r[i][j]=j;
                    while(a[i][l[i][j]-1]>=a[i][j])
                        l[i][j]=l[i][l[i][j]-1];
                }
                for(int j=n;j>=1;j--)
                {
                      while(a[i][r[i][j]+1]>=a[i][j])
                        r[i][j]=r[i][r[i][j]+1];
                }
                for(int j=1;j<=n;j++)
                    maxx=max(maxx,a[i][j]*(r[i][j]-l[i][j]+1));
    
            }
            cout <<maxx*3<<endl;
        }
        return 0;
    }
    
    展开全文
  • 动态规划经典题PPT

    2018-12-01 22:20:45
    相信很多人都对于动态规划很苦恼吧!我也是。。。所以呢给大家带来了这个PPT。(第9章 第3节 动态规划经典题(C++版))
  • acm 动态规划 经典题分析 acm 动态规划 经典题分析 acm 动态规划 经典题分析
  • acm动态规划经典题

    2009-10-06 10:50:56
    acm动态规划经典题,有助于增加对动态规划的理解与应用
  • ACM动态规划经典题

    2010-01-06 20:28:48
    总结的ACM中的动态规划经典题,值得一看
  • 动态规划经典题12道

    2009-07-25 21:21:36
    动态规划经典题,doc格式。共12道,举一反三,希望对初学者有所帮助
  • 动态规划经典习题.pdf

    2019-11-08 07:49:52
    动态规划练习必备,数据结构与算法练习必备,oier训练必备,acmer训练必备,互联网企业训练必备,国企笔试必备
  • 《信息学奥赛一本通》:第9章 第3节 动态规划经典题(C++版)
  • 基础算法 第9章 第3节 动态规划经典题(C++版)-2020.05.16.pdf
  • 里边收集了多个经典动态规划的应用例子,通过学习可以更加深刻地理解动态规划的精髓,对于喜欢算法的朋友会有较大的收获
  • 文章目录题目解题思路(1)基本过程(2)动态规划-递归(3)动态规划-dp table代码 题目 leetCode72:编辑距离 编辑距离算法是一个非常实用的算法,它的作用是求出把一个字符串s1变为另一个字符串s2所需要的最少的...

    题目

    leetCode72:编辑距离
    在这里插入图片描述

    编辑距离算法是一个非常实用的算法,它的作用是求出把一个字符串s1变为另一个字符串s2所需要的最少的操作数
    此过程中,只能对字符串进行插入、删除或替换(其实还有一种隐形操作,就是略过)

    比如把rad变为apple,就需要经过5步
    在这里插入图片描述

    解题思路

    (1)基本过程

    对于字符串类的题目,一般都会使用到两个指针,这里面也不例外。上面的动图中,展现的正是两个指针i和j分别从后向前扫描两个字符串。
    在这个过程中如果j走完了,i还没有走完的话,那么就需要把s1删除,缩短为s2单
    在这里插入图片描述
    如果i走完了,但j没有走完,那么就想要把s2中的插入到s1中

    (2)动态规划-递归

    使用动态规划解题,一定要考虑题目的状态和选择是什么?

    • 状态:这里显然是i和j指针的位置
    • 选择:所选的操作,加上跳过,共有四种操作(skip,insert,delete,replace
    if s1[i]==s2[j]
    	skip;
    else
    	insert or delete or relace;
    

    还有“base case”,也就是最简单的情况是什么呢?这里其实就是上面所叙述的那两种情况

    首先采用递归解法说明。定义一个dp递归函数,函数形参分别就是ij,该函数的返回值就是s1[0....i]s2[0...j]的最小编辑距离,最终一步一步递归,可以得到问题的最终答案。

    现在看该函数的base case,也就是如果j走完了,就把i删除了;如果i走完了,就把j剩下的全部插入

    int dp(i,j)
    {
    	if i==-1
    		return j+1;
    	if j==-1
    		return i+1;
    }
    

    如果遇到的字符相等,那么就什么也不做,直接跳过。也即是说s1[0....i]s2[0....j]的最小编辑距离实际就是s1[0...i-1]s2[0....j-1]的最小编辑距离。

    int dp(i,j)
    {
    	if i==-1
    		return j+1;
    	if j==-1
    		return i+1;
    	if(s1[i]==s[j])
    		return dp[i-1][j-1];
    	else
    	
    }
    

    如果遇到的字符不相等,那么我们就需要进行选择三种操作了。需要注意的是三种操作是肯定存在重叠问题,这也是递归不可避免的问题,因为一个字符变成另一个字符除了可以替换外,我也可以直接插入一个。

    • 第一种操作:插入;递归函数为dp(i,j-1)+1。如果选择了这种操作,那么就会直接在s1[i]中插入一个和s2[j]一样的字符,此时s2[j]会被匹配到。注意操作数+1
      在这里插入图片描述

    • 第二种操作:删除;递归函数为dp(i-1,j)+1。如果选择了这种操作,那么就会直接把s[i]这个字符删除掉。
      在这里插入图片描述

    • 第三种操作:替换;递归函数为dp(i-1,j-1)+1。如果选择了这种操作就会直接把s1[i]替换为s2[j]

    于是伪代码如下

    int dp(i,j)
    {
    	if i==-1
    		return j+1;
    	if j==-1
    		return i+1;
    	if(s1[i]==s[j])
    		return dp[i-1][j-1];
    	else
    		return min(
    		dp(i,j-1)+1;//插入
    		dp(i-1,j)+1;//删除
    		dp(i-1,j-1)+1;//替换
    	)
    }
    

    还是那句话,这种解法一定存在大量重叠子问题。比如能过替换得到的结果也可以通过删除后插入完成,这就是一条重复路径,如果发现了一定重复问题,那么一定会有千千万万个重复问题,就像斐波那契数列一样。而重叠子问题是可以通过备忘录解决的

    memo=dict();
    int dp(i,j)
    {
    	if((i,j) in memo)
    		return memo[(i,j)];
    	if i==-1
    		return j+1;
    	if j==-1
    		return i+1;
    	if(s1[i]==s[j])
    		return dp[i-1][j-1];
    	else
    		return min(
    		dp(i,j-1)+1;//插入
    		dp(i-1,j)+1;//删除
    		dp(i-1,j-1)+1;//替换
    	)
    }
    

    (3)动态规划-dp table

    递归便于说明问题的解决思路,实际写代码时我们一般采用的还是自底向上的解法,也就是动态规划数组。有了上面的基础,我们很容易能够理解,和公共子串,子序列那些题一样**,这道题的数组也一定是一个二维数组**

    在这里插入图片描述
    其中dp[…][0]和dp[0][…]对应的就是base case(也即是把rad变成空串,那么需要3步),dp[i][j]存储的是s1[0…i-1]和s2[0…j-1]的最小编辑距离。(dp函数的base case是i和j为-1,但是数组索引至少为0,所以要偏移1位)

    代码

    class Solution {
    public:
        
        int minDistance(string word1, string word2) 
        {
            int len1=word1.size();
            int len2=word2.size();
            
            vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));//dp数组
            for(int i=1;i<=len1;i++)//base case
                dp[i][0]=i;
            for(int j=1;j<=len2;j++)
                dp[0][j]=j;
            
            for(int i=1;i<=len1;i++)
            {
                for(int j=1;j<=len2;j++)
                {
                    if(word1[i-1]==word2[j-1])
                        dp[i][j]=dp[i-1][j-1];
                    else
                        dp[i][j]=min//min函数只有两个形参,所以这样写
                    (
                        dp[i-1][j]+1,//插入
                        min(dp[i][j-1]+1,//删除
                        dp[i-1][j-1]+1)//替换
                    );
                        
                }
            }
            return dp[len1][len2];
        }
    };
    

    在这里插入图片描述

    展开全文
  • 这道属于贪心算法,但本质仍然是动态规划。对于这样一个棋盘,到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到,要么是前一列(i,j-1)向右移动一列得到 因此我们可以建立一个相同的矩阵gifts,gifts[i][j]表示...

    题目

    牛客
    在这里插入图片描述

    解题思路

    这道题属于贪心算法,但本质仍然是动态规划。对于这样一个棋盘,到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到,要么是前一列(i,j-1)向右移动一列得到
    在这里插入图片描述
    因此我们可以建立一个相同的矩阵gifts,gifts[i][j]表示从起点到i,j这一点中某条路径代表的礼物价值值总和,最终返回数值即可

    这个计算过程中有三个特殊情况

    • 情况1:如果是起点,那么直接忽略即可
    • 情况2:如果处在第一行,那么由于是第一行,所以从起点走,它只可能是向右不断走得到的
    • 情况3:如果处在第一列,那么由于是第一列,所以从起点走,它只可能是向下不断走的到的

    其余情况均是即可向右走,也可以向下走

    代码

    class Bonus {
    public:
        int getMost(vector<vector<int> > board) 
        {
            // write code here
            int length=board.size();
            int width=board[0].size();
            vector<vector<int>> gifts(length,vector<int>(width,0));
            gifts[0][0]=board[0][0];
            for(int i=0;i<length;i++)
            {
                for(int j=0;j<width;j++)
                {
                    if(i==0 && j==0)//情况1
                        continue;
                    else if(i==0)//情况2
                        gifts[i][j]=gifts[i][j-1]+board[i][j];
                    else if(j==0)//情况3
                        gifts[i][j]=gifts[i-1][j]+board[i][j];
                    else//正常情况
                        gifts[i][j]=max(gifts[i-1][j],gifts[i][j-1])+board[i][j];
                }
            }
            
            return gifts[length-1][width-1];//返回到右下角的礼物价值值总和
            
            
        }
    };
    

    在这里插入图片描述

    展开全文
  • 动态规划经典题之最长公共子序列 参考:最长公共子序列与最长公共子串 概念 最长公共子序列: 两个字符串中相同的子串序列,可以不连续。 最长公共子串: 两个字符串中相同的连续子串。 这两者的区别就在于子串是否...

    动态规划经典题之最长公共子序列

    参考:最长公共子序列与最长公共子串

    概念

    最长公共子序列: 两个字符串中相同的子串序列,可以不连续。

    最长公共子串: 两个字符串中相同的连续子串。

    这两者的区别就在于子串是否需要连续。

    状态转移方程

    最长公共子串:

    我们记c[i, j]为x和y在长度为i和j时的最长公共子序列的长度,当x或y的长度为0时,c[i, j]必定为0。当x长度为i,y长度为j时,如果xi == yj,则根据之前计算的结果向前退一位,c[i, j] = c[i-1, j-1] + 1,否则c[i, j] = 0。这是由于连续性导致的。

    756310-20170616234946025-931165217.png

    最长公共子序列:

    同理我们推导最长公共子序列的状态转移方程,i=0或j=0时跟最长公共子串是一样的,但是在i,j>0且xi != yj时,c[i,j]并不是简单的等于0,而是将i或j向前退一位,取c[i-1, j]和c[i, j-1]之间的最大值,这是因为最长公共子序列是可以不连续的。

    756310-20170616234916915-1603057887.png

    代码

    最长公共子串:

    /**
     * 最长公共子串
     * @param s source string
     * @param t target string
     * @return 最长公共子串的长度
     */
    public static int lcs1(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) return 0;
    
        int len1 = s.length(), len2 = t.length();
    
        int[][] dp = new int[len1+1][len2+1];
    
        int max = 0;
    
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                //处理i=0和j=0的情况,自底向上进行初始化
                if (i == 0 || j == 0) dp[i][j] = 0;
                else if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = 0;
                }
    
                if (max < dp[i][j])
                    max = dp[i][j];
            }
        }
    
        return max;
    }

    最长公共子序列:

    /**
     * 最长公共子序列
     * @param s source string
     * @param t target string
     * @return 最长公共子序列的长度
     */
    public static int lcs(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) return 0;
    
        int len1 = s.length(), len2 = t.length();
    
        int[][] dp = new int[len1+1][len2+1];
    
        int max = 0;
    
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0 || j == 0) dp[i][j] = 0;
                else if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    //和最长公共子串不一样的地方
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
    
                if (max < dp[i][j])
                    max = dp[i][j];
            }
        }
    
        return max;
    }

    转载于:https://www.cnblogs.com/puyangsky/p/7048606.html

    展开全文
  • 某大牛总结的动态规划学习指南,以pku题目为重点讲解,对于正迷茫于动态规划的ACM,OI选手有很大帮助。
  • HDU 动态规划经典题

    2017-07-03 16:49:59
    找j,k成为关键,一般方法肯定超时,利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边界一定满足这个性质,再从这个边界的左边迭代下去 for(i= 1 ;i;i++) { while(a[l[i]- 1 ]>=a[i]) l[i]=l[l[i]- 1...
  • 动态规划经典题讲解

    2017-07-25 11:26:25
    方法三:动态规划 案例二:给定给一个矩阵m,从左上角开始每次只能向右或者向下走,最后到达右下角的位置。路径上所有的数字累加起来就是路径和,返回所有的路径中最小路径和。 如果给定的m如大家看到的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,786
精华内容 714
关键字:

动态规划经典题