服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - c++动态规划经典算法

c++动态规划经典算法

2021-12-16 14:27静笃归心方得平和心气 C/C++

动态规划算法通常用于求解具有某种最优性质的问题。本文主要介绍了c++动态规划经典算法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

基本思想

         动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

重要分析问题方法

        动态规划算法跟数组有着密切的关系，因此推荐大家在分析动态规划的算法时画一张表格（建议使用excel）分析解决问题往往能够事半功倍。

动态规划算法实例

1、台阶问题

 问题描述：有10级台阶，一个人每次上一级或者两级，问有多少种走完10级台阶的方法。

结合表格分析问题，每个子问题都只跟台阶这个变量相关，可以画出一个一维表格进行分析。

　 1 2 3 4 5 6 7 8 9 10
走法 1 2 3 5 8 13 21 34 55 89

分析边界条件：对于每个台阶每次上一级或者两级，当台阶数为1时走法为1（即走一级即毕）为2时走法为2（走两次一级和走一次二级）。

分析递归关系：对于任一台阶都可以分为通过两级或者一阶到达。

c++动态规划经典算法      

终于，在有了上述两个条件之后，问题轻易得到了求解。（结合表格分析的手段到这里还没有完全发挥出它该有的优势，大家拭目以待）

台阶问题基于c++的代码实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。
//
//台阶问题：有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
#include "stdafx.h"
#include <iostream>
using namespace std;
int getResultByDP(int n)//自底向上的问题解法
{
    if (n<1)
    {
        return 0;
    }
    if (n==1)
    {
        return 1;
    }
    if (n==2)
    {
        return 2;
    }
    int a = 1;//从两个递归基开始
    int b = 2;
    int temp = 0;
    for (int i = 3; i < n + 1; i++)
    {
        temp = a + b;
        a = b;
        b = temp;
    }
    return temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
    cout << getResultByDP(10);
    system("pause");
    return 0;
}

2、从矩阵左上角走到右下角最短路径问题

问题描述：给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.

1 3 5 9

8 1 3 4

5 0 6 1

8 8 4 0

 

矩阵从左上角走到右下角
　 0 1 2 3 4
0 0 0 0 0 0
1 0 1 3 5 9
2 0 8 1 3 5
3 0 5 0 6 1
4 0 8 8 4 0
　 　 　 　 　 　
　 0 1 2 3 4
0 0 0 0 0 0
1 0 1 4 9 18
2 0 9 5 8 13
3 0 14 5 11 12
4 0 22 13 15 12

 

边界条件分析：由问题知道对于任一矩阵中的元素而言，上次位置或者是在该元素的坐标或者上边。那么当一些元素没有左边或者上边时应该怎么做呢？不妨就说的更为具体一些吧，如上图的表格所示当x(表示行下标)等于1，和y（表示列下标）等于1时正好是对应没有上边元素和没有左边元素的情况。对于只有左边元素的值array[x][y]=array[x][y-1]+m[x][y],对于只有上边元素:array[x][y]=array[x-1][y]+m[x][y]（array为下面统计问题结果的二维数组，m为包含输入矩阵信息的二维数组）。

递归公式：对于平凡的子问题而言 （推导递归公式时刻意的考察array[x][y]和array[x-1][y]与array[x][y-1]的实际关系）

对于此问题而言：arry[x][y]=min(array[x-1][y],array[x][y-1])+m[x][y]

以下是该问题基于c++的代码实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int const x_length=5, y_length=5;
int m[x_length][y_length] = {
    0, 0, 0, 0, 0,
    0, 1, 3, 5, 9,
    0, 8, 1, 3, 5,
    0, 5, 0, 6, 1,
    0, 8, 8, 4, 0
};
int minDis() //m二级指针（可以是一个二维数组）
{
    int dp[4 + 1][4 + 1];
    //---------初始化边界条件-----------------
    for (size_t i = 0; i < x_length; i++)
    {
        dp[i][0] = 0;
    }
    for (size_t j = 0; j < y_length; j++)
    {
        dp[0][j] = 0;
    }
    //-------------------------------------------
    for (size_t i = 1; i < x_length; i++)
    {
        for (size_t j= 1; j < y_length; j++)
        {
            if (i == 1)
            {
                dp[i][j] = dp[i][j - 1] + m[i][j];
            }
            else if (j == 1)
            {
                dp[i][j] = dp[i - 1][j] + m[i][j];
            }
            else
            {
                int temp1 = dp[i - 1][j] + m[i][j];
                int temp2 = dp[i][j - 1] + m[i][j];
                dp[i][j] = min(temp1, temp2);
            }          
        }
    }
    return dp[x_length - 1][y_length - 1];
}
int _tmain(int argc, _TCHAR* argv[])
{
    cout << "最右下角的最短路径为：" << minDis();
    system("pause");
    return 0;
}

3、最大子数组问题

问题描述：给定数组arr，返回arr的最长递增子序列的长度，比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]返回其长度为5，由于该问题中总要把当前元素和在他之前的进行分析，我们也是借助表格来直观的分析该问题。

　 　 2 4 5 3 1 　 　
　 　 0 1 2 3 4 5 6
2 0 　 　 　 　 　 　 　
4 1 　 　 　 　 　 　 　
5 2 　 　 　 　 　 　 　
3 3 　 　 　 　 　 　 　
1 4 　 　 　 　 　 　 　
　               　
0 1 2 3 4       　
1 2 3 2 1 　 　 　 　

边界条件：显然对于第一个数而言有dp[0]=1(dp表示存放结果的数组)

递归公式：首先生成dp[n]的数组，dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说，很明显dp[0]为1，当我们计算dp[i]的时候，我们去考察i位置之前的所有位置，找到i位置之前的最大的dp值，记为dp[j](0=<j<i),dp[j]代表以arr[j]结尾的最长递增序列，而dp[j]又是之前计算过的最大的那个值，我们在来判断arr[i]是否大于arr[j],如果大于dp[i]=dp[j]+1.计算完dp之后，我们找出dp中的最大值，即为这个串的最长递增序列。

该问题基于c++的代码实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//给定数组arr，返回arr的最长递增子序列的长度，比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]返回其长度为5.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[5] = {};
int _tmain(int argc, _TCHAR* argv[])
{
 int arr[5] = { 2, 4, 5, 3, 1 };
 dp[0] = 1;
 const int oo = 0;
 for (int i = 1; i<5; i++){
  int _max = oo;
  for (int j = 0; j<i; j++)
   if (dp[j]>_max && arr[i]>arr[j])
    _max = dp[j];
  dp[i] = _max + 1;
 }
 int maxlist = 0;
 for (int i = 0; i < 5; i++)
  if (dp[i] > maxlist)
   maxlist = dp[i];
 cout << maxlist << endl;
 system("pause");
 return 0;
}

4、最长公共子序列

问题描述：给定两个字符串str1和str2，返回两个字符串的最长公共子序列，例如：str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"和"12C4B6"都是最长公共子序列，返回哪一个都行。

问题分析：首先生成dp[n]的数组，dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说，很明显dp[0]为1，当我们计算dp[i]的时候，我们去考察i位置之前的所有位置，找到i位置之前的最大的dp值，记为dp[j](0=<j<i),dp[j]代表以arr[j]结尾的最长递增序列，而dp[j]又是之前计算过的最大的那个值，我们在来判断arr[i]是否大于arr[j],如果大于dp[i]=dp[j]+1.计算完dp之后，我们找出dp中的最大值，即为这个串的最长递增序列。

 

　 　 B D C A B A 　
　 　 0 1 2 3 4 5 　
A 0 0 0 0 0 0 0 0
B 1 0 0 0 0 1 1 1
C 2 0 1 1 1 1 2 2
B 3 0 1 1 2 2 2 2
D 4 0 1 1 2 2 3 3
A 5 0 1 2 2 2 3 3
B 6 0 1 2 2 3 3 4
　 7 0 1 2 2 3 4 4
　 　 　 　 　 　 　 　 　
　 　 B D C A B A 　
　 　 0 1 2 3 4 5 　
A 0 -2 -2 -2 -2 -2 -2 -2
B 1 -2 -1 -1 -1 0 1 0
C 2 -2 0 1 1 -1 0 1
B 3 -2 -1 -1 0 1 -1 -1
D 4 -2 0 -1 -1 -1 0 1
A 5 -2 -1 0 -1 -1 -1 -1
B 6 -2 -1 -1 -1 0 -1 0
　 7 -2 0 -1 -1 -1 0 -1

 

该问题基于c++代码实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//输入为两个长度不为零的字符串，输出这两个字符串的最大公共子序列
#include "stdafx.h"
#include <string>
#include <iostream>
#ifndef MAX
#define MAX(X,Y) ((X>=Y)? X:Y)
#endif
using namespace std;
int **Lcs_length(string X, string Y, int **B)
{
 int x_len = X.length();
 int y_len = Y.length();
 int **C = new int *[x_len + 1];
 for (int i = 0; i <= x_len; i++)
 {
  C[i] = new int[y_len + 1];        //定义一个存放最优解的值的表；
 }
 for (int i = 0; i <= x_len; i++)
 {
  C[i][0] = 0;
  B[i][0] = -2;                     //-2表示没有方向
 }
 for (int j = 0; j <= y_len; j++)
 {
  C[0][j] = 0;
  B[0][j] = -2;
 }
 for (int i = 1; i <= x_len; i++)
 {
  for (int j = 1; j <= y_len; j++)
  {
 
   if (X[i - 1] == Y[j - 1])
   {
    C[i][j] = C[i - 1][j - 1] + 1;
 
    B[i][j] = 0;             //0表示斜向左上
   }
   else
   {
    if (C[i - 1][j] >= C[i][j - 1])
    {
     C[i][j] = C[i - 1][j];
     B[i][j] = -1;       //-1表示竖直向上；
    }
    else
    {
     C[i][j] = C[i][j - 1];
     B[i][j] = 1;        //1表示横向左
    }
   }
 
  }
 }
 return C;
}
 
void OutPutLCS(int **B, string X, int str1_len, int str2_len)
{
 if (str1_len == 0 || str2_len == 0)
 {
  return;
 }
 if (B[str1_len][str2_len] == 0)   //箭头斜向左上
 {
  OutPutLCS(B, X, str1_len - 1, str2_len - 1);
  cout << X[str1_len - 1] << endl;
 }
 else if (B[str1_len][str2_len] == -1)
 {
  OutPutLCS(B, X, str1_len - 1, str2_len);
 }
 else
 {
  OutPutLCS(B, X, str1_len, str2_len - 1);
 }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
 string X = "ABCBDAB";
 string Y = "BDCABA";
 
 int x_len = X.length();
 int y_len = Y.length();
 
 int **C;//定义一个二维数组
 
 int **B = new int *[x_len + 1];
 for (int i = 0; i <= x_len; i++)
 {
  B[i] = new int[y_len + 1];
 }
 C = Lcs_length(X, Y, B);
 for (int i = 0; i <= x_len; i++)
 {
  for (int j = 0; j <= y_len; j++)
  {
   cout << C[i][j] << " ";
  }
  cout << endl;
 }
 cout << endl;
 for (int i = 0; i <= x_len; i++)
 {
  for (int j = 0; j <= y_len; j++)
  {
   cout << B[i][j] << " ";
  }
  cout << endl;
 }
 OutPutLCS(B, X, x_len, y_len);//构造最优解
 system("pause");
 return 0;
}

到此这篇关于c++动态规划经典算法的文章就介绍到这了,更多相关c++动态规划内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/weixin_42182348/article/details/90814032

  • C++
  • 动态规划

    • 延伸 · 阅读

    精彩推荐
    • C/C++OpenCV实现拼接图像的简单方法

      OpenCV实现拼接图像的简单方法

      这篇文章主要为大家详细介绍了OpenCV实现拼接图像的简单方法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      iteye_183805102021-07-29
    • C/C++使用C++制作简单的web服务器（续）

      使用C++制作简单的web服务器（续）

      本文承接上文《使用C++制作简单的web服务器》，把web服务器做的功能稍微强大些，主要增加的功能是从文件中读取网页并返回给客户端，而不是把网页代码...

      C++教程网5492021-02-22
    • C/C++c/c++内存分配大小实例讲解

      c/c++内存分配大小实例讲解

      在本篇文章里小编给大家整理了一篇关于c/c++内存分配大小实例讲解内容，有需要的朋友们可以跟着学习参考下。...

      jihite5172022-02-22
    • C/C++C语言main函数的三种形式实例详解

      C语言main函数的三种形式实例详解

      这篇文章主要介绍了 C语言main函数的三种形式实例详解的相关资料,需要的朋友可以参考下...

      ieearth6912021-05-16
    • C/C++C语言实现双人五子棋游戏

      C语言实现双人五子棋游戏

      这篇文章主要为大家详细介绍了C语言实现双人五子棋游戏，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      两片空白7312021-11-12
    • C/C++c/c++实现获取域名的IP地址

      c/c++实现获取域名的IP地址

      本文给大家汇总介绍了使用c/c++实现获取域名的IP地址的几种方法以及这些方法的核心函数gethostbyname的详细用法，非常的实用，有需要的小伙伴可以参考下...

      C++教程网10262021-03-16
    • C/C++关于C语言中E-R图的详解

      关于C语言中E-R图的详解

      今天小编就为大家分享一篇关于关于C语言中E-R图的详解，小编觉得内容挺不错的，现在分享给大家，具有很好的参考价值，需要的朋友一起跟随小编来看看...

      Struggler095962021-07-12
    • C/C++深入C++拷贝构造函数的总结详解

      深入C++拷贝构造函数的总结详解

      本篇文章是对C++中拷贝构造函数进行了总结与介绍。需要的朋友参考下...

      C++教程网5182020-11-30
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 素数交换 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 C语言程序设计 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图