• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

动态规划练习合集(c++)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
最近一直在刷动态规划的题目,深感动态规划的难度。于是复习一下最近刷的题,加深记忆。
关于什么是动态规划,可以去看百度文库的解释https://baike.baidu.com/item/动态规划/529408,不过说的十分混乱,难以理解。也可以去看看维基百科的解释https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92。

做了这么多的题目,大致的思路是建立合适的容器存放数据,寻找最优子结构,编码。
//建立容器,初始化容器,依据最优子结构循环产生数据,输出结构

闲话少叙——上题目
 
/******************************************************************************/
例题1:硬币问题,现在有1,3,5面值的硬币无限数量。给定金额x,求使用最少的硬币组合出x元。分别求出总硬币数量,硬币使用个数。
思考:如果m[x]表示x元需要的硬币个数,m[x] = min{m[x-1]+1 ; m[x-3]+1 ; m[x-5]+1} ;
因为要求使用的各个硬币个数,还要建立一个node节点来记录,采用备忘录方法回求解。

typedef struct {
    int nCoin; //使用硬币数量
    //以下两个成员是为了便于构造出求解过程的展示
    int lastSum;//上一个状态
    int addCoin;//从上一个状态达到当前状态所用的硬币种类
} state; 

int main()
{
    //用户输入总额
    int total;
    cin >> total ;
    
    //建立动态规划的容器
    state *m = new state[total+1];
    
    //初始化数据
    for(int i=0;i<=total;i++) 
        m[i].nCoin = total;
    m[0].nCoin = 0;
    m[0].lastSum = 0;
    
    //初始化数据——准备硬币和0,1,2之间的对应关系
    int n =  3 ;
    int * coin = new int[3];
    coin[0] = 1;
    coin[1] = 3;
    coin[2] = 5; 
    
    //循环求解-外层循环之后,需要比较三次才能知道答案,也使用了循环。
    for(int i=1;i<=total;i++)
        for(int j=0;j<n;j++)
            if(i-coin[j]>=0 && m[i-coin[j]].nCoin+1 < m[i].nCoin)
            {
                m[i].nCoin = m[i-coin[j]].nCoin+1;
                m[i].lastSum = j;
                m[i].addCoin = coin[j];
            }
    //根据内容回推解。
    int i =  total; 
    while(i > 0)
    {
        cout << "使用" << m[i].addCoin << "一次" << endl;
        i = i- coin[m[i].lastSum]; 
    }     
    return 0;
 } 
 
 很简单的题目,最优子结构很容易就想到了,不过很适合做第一个练习,去熟悉和了解动态规划。
 
/******************************************************************************/
例题2:苹果装配问题,把一个区域分成n*m个小区域,其中每个区域有一定数量的苹果,设左上角为0,0,右下角为n-1,m-1.从0,0开始出发,每经过一个区域,就把该区域的苹果全部收走,求一条路径使得收获的苹果最多。
思考:刚才做了一个动态规划的题目,应该知道现在需要去寻找最优子结构。这题应该使用一个二维数组来存放数据,设为v[m+1][n+1].
v[i][j]表示的含义是到达i行j列可以获得的苹果数量。v[i][j] = max{v[i-1][j]+A[i][j] ; v[i][j-1]+A[i][j]};(A[i][j]表示第i行第j列苹果个数)。
class Node{
public:
    int numOfApple;
    int lastOperation_x;
    int lastOperation_y;
    Node(){
        numOfApple = 10000;
        lastOperation_x = 0;
        lastOperation_y = 0;
    } 
} ;

int main()
{
    //准备数据,建立一个3*4的区域
    //numApple表示数据信息是一个二维数组。类型是int
    vector<vector <int > > numApple;
    Node node[3][4];
    
    //循环求出解,初始化数据也放在其中
    for(int x = 0 ; x < 3; x++ )
    {
        for(int y = 0; y < 4;y++)
        {
            //第一个数据 
            if(x == 0 && y ==0)
            {
                node[x][y].numOfApple = numApple[x][y];
                continue;
            }
            if(x == 0)
            {
                node[x][y].numOfApple = node[x][y-1].numOfApple + numApple[x][y] ;
                node[x][y].lastOperation_y = 1;//表示向前移动 
                continue;
            } 
            if(y == 0)
            {
                node[x][y].numOfApple = node[x-1][y].numOfApple + numApple[x][y] ;
                node[x][y].lastOperation_x = 1;//表示向后移动。 
                continue;
            } 
            
            if(node[x][y-1].numOfApple > node[x-1][y].numOfApple)
            {
                node[x][y].numOfApple = node[x][y-1].numOfApple + numApple[x][y] ;
                node[x][y].lastOperation_y = 1;//表示向前移动 
            } 
            else
            {
                node[x][y].numOfApple = node[x-1][y].numOfApple + numApple[x][y] ;
                node[x][y].lastOperation_x = 1;//表示向后移动。 
            }    
        }    
    }
    //输出求出的数据
    cout << "一共可以有" <<node[2][3].numOfApple <<endl; 
    //也可以通过节点的信息,求出解的过程。
    return 0;
}

这个题目应该比较容易理解,这是最简单的动态规划。下面还有一些题目,如果难度大的题目做不出来可以拿下面的几题提高自信心。lintcode相似的题目:

110. 最小路径和  https://www.lintcode.com/problem/minimum-path-sum/description
114. 不同的路径  https://www.lintcode.com/problem/unique-paths/description
115. 不同的路径 II https://www.lintcode.com/problem/unique-paths-ii/description

/******************************************************************************/
例题3:装配调度问题。(如果描述的不清楚可以百度看看详细的题目)
一个公司有两条生产线,每个生产线有6个生产工序,各个生产线的相同生产工序时间不同,
从一个生产线的一个工序生产之后可以继续在该生产线上生产,也可以在另一个生产线上胜场。
相同的生产线工序移动不需要时间,不同之间需要时间,求最短的时间。
需要的时间按照顺序是:
    从外界装配到生产线i1,生产线A1工序花费v1,从A1到A2不需要花费,但是如果切换到B2生产就需要时间x1,A2的工序花费为v2
    .....
    最后从生产线上下来,也需要o1时间。
思考:题目很复杂,但是原理很简单,化简出来就是两条生产线,每条生产线上有若干个工序,每个工序花费一定的时间。不同的生产线花费的时间是不一样的。如果在一个生产线上从一个工序到另一个工序不需要时间,如果切换到别的生产线上需要时间。求最短的时间?
设计一个容器m[x][2],x表示一共有多少工序。m[i][j]含义是第i个工序,第j个生产线需要的时间。
不难得知m[i][0] = min{m[i-1][0]+A[i];m[i-1][1]+C[i]+A[i]},这个公式是用来计算第一行数据的,如果是第二行则为m[i][1] = min{m[i-1][1]+A[i];m[i-1][0]+C[i]+A[i]},其中A[i]表示第i个工序的时间,C[i]表示切换需要的时间。

代码如下:
//用来回推最优解
class station
{
    public :
        int curTime;//当前站点已经消耗的时间
        int lastQueue;//上一次的队列。
    station()
    {
        curTime = 10000;
        lastQueue = 0;    
    } 
};

int main()
{
    
    //准备数据,这是一个具有6个工序的两个生产线。
    int statTime[2][6] = {7,9,3,4,8,7,812,5,6,4,5,9};
    int charge1Time[5] = {2,3,1,3,4};
    int charge2Time[5] = {2,1,2,2,1};
    int in1 = 2;
    int in2 = 4;
    int out1 = 3;
    int out2 = 2;
    
    //建立容器
    station stat[2][6];
    int i ;
    int j ;
    
    //循环求每一个数据位置的解
    for(j = 0 ; j < 6 ; j ++)
    {
        for(i = 0 ; i < 2;i++)
        {
            //如果是第一个的话 
            if(j == 0)
            {
                stat[i][j].curTime = statTime[i][j];
                continue;
            }
            //求当前在第一条生产线上 
            if(i%2 == 0)
            {
                 //第一行 
                if(stat[i][j-1].curTime > stat[i+1][j-1].curTime+charge2Time[j-1])
                {
                    //需要换行
                    stat[i][j].curTime = stat[i+1][j-1].curTime+charge2Time[j-1]+statTime[i][j];
                    stat[i][j].lastQueue = 2; 
                }
                else
                {
                    //不需要换行 
                    stat[i][j].curTime = stat[i][j-1].curTime+statTime[i][j];
                    stat[i][j].lastQueue = 1; 
                }
            } 
            else
            {
                //在第二行 
                if(stat[i][j-1].curTime > stat[i-1][j-1].curTime+charge1Time[j-1])
                {
                    //需要换行
                    stat[i][j].curTime = stat[i-1][j-1].curTime+charge1Time[j-1]+statTime[i][j];
                    stat[i][j].lastQueue = 1; 
                }
                else
                {
                    //不需要换行 
                    stat[i][j].curTime = stat[i][j-1].curTime+statTime[i][j];
                    stat[i][j].lastQueue = 2; 
                }
            } 
        }
    }
    cout << stat[0][5].curTime<<endl;
    cout << stat[1][5].curTime <<endl;
} 

装配问题思路并不是很复杂,应该还是很容易想到的。

/******************************************************************************/
例题4:给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。
        你总共三种操作方法:
        插入一个字符
        删除一个字符
        替换一个字符
分析:这个题目是处理两个字符串相关问题的。一般字符串相关的算法都是使用动态规划。
建立一个容器m[len1][len2],其中len1和len2分别表示单词的长度。m[i][j]表示如果第一个单词取前面的i个第二个单词取后面的j个需要调整的次数。
如果m[i][j]插入一个数据,m[i][j] = m[i][j-1]+1。
如果m[i][j]删除一个数据,m[i][j] = m[i-1][j]+1.
如果m[i][j]中有一个字符相等,则有m[i][j] = m[i-1][j-1](+1如果是替换需要增加1)
通过这些从上面的数据中找到最小的就可以了。m[i][j] = min{m[i-1][j-1] + 0/1,m[i-1][j]+1,m[i][j-1]+1 }

代码如下:
//记录最优解的信息。
class memo{
public:
    int time;//这个节点的次数
    int lastOpt;//上一个操作是0修改,1插入,2删除。 
    memo()
    {
        time = 0 ; 
        lastOpt = 0;
    }
};

class Solution {
public:
    int match(char d,char s)
    {
        if(d == s)
        {
            return 0; 
            //如果相等返回0        
        }    
        else
        {
            return 1;
        } 
    } 
    int minDistance(string &word1, string &word2) {
        
        //准备数据,动态建立一个二维数组,记着使用delete删除空间哦
        int len_1 = word1.length();
        int len_2 = word2.length(); 
        memo ** m = new memo*[len_2+1];
        for(int i = 0 ; i < len_2+1 ; i++) 
        {
            m[i] = new memo[len_1+1];
        }
        
        //对边缘经行初始化
        for(int i = 0 ; i < len_2+1 ; i++)
        {
            //如果B有i个数据,A没有数据,需要做的调整就只有插入, 
            m[i][0].time = i;
        }
        for(int j = 0 ; j < len_1+1; j++)
        {
            //如果B中没有数据,A中数据,需要做的调整就是删除。 
            m[0][j].time = j; 
        } 
        
        //循环求出每一个数据的值
        int i ,j;
        for(i = 1 ; i < len_2+1; i++)
        {
            for(j = 1 ;j < len_1+1; j++)
            {
                //计算3中情况 
                int way1 = m[i-1][j-1].time + this->match(word2[i-1],word1[j-1]); //判断最后一个是否相同的。 
                
                int way2 = m[i-1][j].time+1;
                
                int way3 = m[i][j-1].time+1;
                
                //取其中的最小值。
                if(way1 > way2)
                {
                    if(way2 > way3)
                    {
                        m[i][j].time = way3;
                        m[i][j].lastOpt = 3;        
                    }        
                    else
                    {
                        m[i][j].time = way2;    
                        m[i][j].lastOpt = 2;
                    }
                }
                else
                {
                    if(way1 > way3)
                    {
                        m[i][j].time = way3;
                        m[i][j].lastOpt = 3;        
                    }        
                    else
                    {
                        m[i][j].time  = way1;
                        m[i][j].lastOpt = 1;    
                    }
                }    
             
            }
         } 
    
    //输出数据
    cout << "需要调整的次数:" << m[len_2][len_1].time <<endl;
    int ret = m[len_2][len_1].time;
    delete [] m;
    return ret;
    }
};

//这是lintcode上面的一个题目,是学习动态规划路上看着代码分析的。下面几个题目都是字符串相关的动态规划问题。

/******************************************************************************/
例题5:给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。
    例如:比如 s1 = "aabcc" s2 = "dbbca";当 s3 = "aadbbbaccc", 返回 false.当 s3 = "aadbbcbcac",返回  true.

思路:这个题目我使用了两种方法来实现,第一中使用回溯法,判断s3中的数据是s1的还是s2的,如果都是就记录一下,如果都不是就返回记录的点。第二种是动态规划:之前需要建立容器bool m[len1][len2]其中len1表示s1的长度,len2表示len2的长度。因为s3的长度一定是s1和s2的长度之和,
所以m[i][j]表示的内容是如果s1区长度i,s2取长度j,则s3也应该取i+j的长度。
则有m[i][j] = m[i][j-1] && s1[i] == s2[j] || m[i-1][j] && s1[i] == s2[j]


代码如下:
class Solution {
public:
    bool isInterleave(string &s1, string &s2, string &s3) {
        
        //建立一个i+1和j+1的数组
        if(s1.length() + s2.length() != s3.length())
        {
            return false;
        }
        bool ** m = new bool*[s2.length()+1];
        for(int i = 0;i<s2.length()+1;i++)
        {
            m[i] = new bool [s1.length()+1];
        }    
        
        //初始化数据
        //如果B中没有数据,只有A中有数据
            
        m[0][0] = true; 
        
        for(int i = 1 ; i < s1.length()+1;i++)
        {
            //如何判断是否是true
            //如果前面是true ,而且现在也是相等的 
            m[0][i] = m[0][i-1] && s1.at(i-1) == s3.at(i-1); 
        } 
        
        for(int i = 1 ; i < s2.length()+1;i++)
        {
            //如何判断是否是true
            //如果前面是true ,而且现在也是相等的 
            m[i][0] = m[i-1][0] && s2.at(i-1) == s3.at(i-1); 
        } 
        
        for(int i = 1;i < s2.length()+1;i++)
        {
            for(int j = 1 ; j < s1.length()+1;j++)
            {
                //默认情况下
                m[i][j] = false;
                //如果s1[i]和s3[i+j] 相等,而且m[i-1][j] == true;
                //如果s1[j]和s3[i+j] 相等,而且m[i][j-1] ==true; 
                if(s1[j-1] == s3[i+j-1])
                {
                    m[i][j] = m[i][j-1] ;    
                } 
                if(s2[i-1] == s3[i+j-1])
                {
                    m[i][j] = m[i][j] || m[i-1][j] ;    
                }     
            }
        }
        return m[s2.length()][s1.length()];
    }
};

/******************************************************************************/
例题6:最长公共子序列  lintcode:77题
给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。
给出"ABCD""EDCA",这个LCS是 "A" (或 D或C),返回1
给出 "ABCD""EACB",这个LCS是"AC"返回 2

思考:给定两个字符串,返回最长的公共子序列的长度。因为是两个字符串,很容易的想到采用一个二维数组来记录问题的解。
定义一个变量m[len1][len2],其中len1表示s1的长度,len2表示len2的长度。值m[i][j]表示的含义是如果s1取i个,s2取j个,他们的公共子序列的长度。m[i][j] =  if(s1[i] == s[j]) {m[i-1][j-1]} else {min{m[i-1][j},m[i][j-1]}}

代码如下:
class Solution {
public:
    int longestCommonSubsequence(string &A, string &B) {
        
        //建立一个容器用来存放数据
        int **m = new int* [A.length()+1];
        for(int i = 0 ; i < A.length()+1;i++)
        {
            m[i] = new     int [B.length()+1];
        }
        
        //初始化数据
        m[0][0] = 0;
        for(int i = 0 ; i < A.length()+1;i++)
        {
            m[i][0] = 0;    
        } 
        for(int i = 0 ; i < B.length()+1;i++)
        {
            m[0][i] = 0;    
        } 
        
        //循环处理数据
        for(int i = 1 ; i < A.length()+1;i++)
        {
            for(int j = 1 ; j < B.length()+1;j++)
            {
                //涉及2个结果需要比较
                //仅仅需要比较一侧就可以了 
                //针对两个条件进行判断
                if(A.at(i-1) == B.at(j-1)) 
                {
                    m[i][j] = m[i-1][j-1] + 1;
                }
                else
                {
                    if(m[i][j-1] < m[i-1][j])    
                    {
                        m[i][j]    = m[i-1][j];
                    }
                    else
                    {
                        m[i][j] = m[i][j-1];
                    }
                }
            }
        } 
        
        //cout << m[A.length()][B.length()];
        return m[A.length()][B.length()];
    }
};

/******************************************************************************/
例题7:最长上升子序列 lintcode:76题
给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。
给出 [5,4,1,2,3],LIS 是 [1,2,3],返回 3
给出 [4,2,4,5,3,7],LIS 是 [2,4,5,7],返回 4

思路:这个题目和以往的题目都不同,以往都是字符串,而且一般都是两个,很容易就想到要设置m[i][j]这样的容器。这个题目只有一个序列,采用什么容器,最优子结构是什么都比较困难。
看了答案之后,才知道这个题目只需要一维数组就可以了,m[len+1],其中len+1表示序列的长度,m[i]表示的值就是只取前面的i
个数据,最长的长度。
m[i] = max{if(a[i] > a[k]) m[k] + 1}//其中k是0~i-1的整数。
代码如下:
class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> &nums) {
       //建立容器
       int * m = new int [nums.size()];
       int ret = 0 ;
       
       //初始化数据
       m[0] = 1;
       
       //执行递推关系
       
       for(int i = 1 ; i < nums.size();i++)
       {
               m[i] = 1;
               for(int j = 0 ; j < i ; j++)
               {
                   if(nums.at(i) > nums.at(j))
                {
                    if(m[i] < m[j] + 1 )
                        m[i] = m[j] + 1;           
                }    
            }
            if(ret < m[i])
            {
                ret = m[i];
            }
       } 
       return ret ;
    }
};

/******************************************************************************/
例题8:最小调整代价 lintcode:91题
给一个整数数组,调整每个数的大小,使得相邻的两个数的差不大于一个给定的整数target,调整每个数的代价为调整前后的差的绝对值,求调整代价之和最小是多少。(整数的大小不超过100.)
对于数组[1, 4, 2, 3]和target=1,最小的调整方案是调整为[2, 3, 2, 3],调整代价之和是2。返回2。

思路:这个题目我认为是非常的难的,我想了很久都没想到。存放数据的容器就很难想象的到,定义一个m[i][100]的容器。
这个题目我是看了答案的,容器定义成为m[A.size()][100],A.size()表示序列的长度,m[i][j]表示为第i个元素如果调整成j,需要花费的最小代价。(i之前的数据都是有意义,而且是最小的调整代价)
所以有m[i][j] = min{ m[i-1][j+k] //其中k的值表示为-target,+target之间的所有数据}

代码如下:
class Solution {
public:
    int MinAdjustmentCost(vector<int> &A, int target) {
       
       if(A.size() == 1 || A.size() ==  
                       
                    
                    

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
使用C#开发ActiveX控件发布时间:2022-07-13
下一篇:
C++中的RAII介绍发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap