盖子的c++小课堂——第二十二讲：2维dp_二维dp

前言

大家好，我又来更新了，今天终于有时间了aaaaaaaa

破500粉了，我太高兴了哈哈哈哈哈哈（别看IP地址，我去北京旅游回来了，他没改回来），然后我马上就成为创作者一年了，希望大家别取关啊，一会儿没更新，粉丝就刷刷往下掉（我刚破的510啊┭┮﹏┭┮）

哎哎，话不多说，我们开始吧（诶诶！先别直接退，这次可花了我一个多小时写的，麻烦看到底吧）

二维递推、二维动态规划

要理解二维递推、二维动态规划，我们先分别讲一下一维数组和二维数组。

什么是数组

在程序中，经常需要对一批数据进行操作，例如，统计某个公司100个员工的平均工资。如果使用变量来存放这些数据，就需要定义100个变量，显然这样做很麻烦，而且很容易出错。这时，可以使用X[0]、X[1]、X[2]、…、X[99]表示这100个变量，并通过方括号中的数字来对这100个变量进行区分。
在程序设计中，使用X[0]、X[1]、X[2]、…、X[99]表示的一组具有相同数据类型的变量集合称为数组X，数组中的每一项称为数组的元素,每个元素都有对应的下标(n)，用于表示元素在数组中的位置序号，该下标是从0开始的。

 需要注意的是，根据数据的复杂度,数组下标的个数是不确定的。通常情况下，数组元素下标的个数也称为维数，根据维数的不同，可将数组分为一维数组、二维数组、三维数组、四维数组等。通常情况下，我们将二维及以上的数组称为多维数组。

一维数组

一维数组的定义与初始化

一维数组指的是只有一个下标的数组，它用来表示一组具有相同类型的数据。在C语言中，一维数组的定义方式如下所示：

类型说明符 数组名[常量表达式];

在上述语法格式中，类型说明符表示数组中所有元素的类型，常量表达式指的是数组的长度，也就是数组中存放元素的个数。

例：

int array[5l;

上述代码定义了一个数组，其中，int是数组的类型，aray是数组的名称，方括号中的5是数组的长度。完成数组的定义后，只是对数组中的元素开辟了一块内存空间。这时，如果想使用数组操作数据，还需要对数组进行初始化。数组初始化的常见的方式有3种，具体如下

（1）直接对数组中的所有元素赋值，示例代码如下：

int i[5]={1,2,3,4,5};

上述代码定义了一个长度为5的数组i，并且数组中元素的值依次为1、2、3、4、5。

（2）只对数组中的一部分元素赋值，示例代码如下

int i[5]={1,2,3};

在上述代码中，定义了一个int类型的数组，但在初始化时，只对数组中的前3个元素进行了赋值，其他元素的值会被默认设置为

（3）对数组全部元素赋值，但不指定长度，示例代码如下：

int i[]={1,2,3,4};

在上述代码中，数组i中的元素有4个，系统会根据给定初始化元素的个数定义数组的长度,因此，数组i的长度为4。

注意！（1）数组的下标是用方括号括起来的，而不是圆括号；（2）数组名的命名同变量名的命名规则相同；（3）数组定义中，常量表达式的值可以是符号常量，如下面的定义就是合法的。

int a[N];      //假设预编译命令#define N 4，下标是符号常量

一维数组的引用

在程序中，经常需要访问数组中的一些元素，这时可以通过数组名和下标来引用数组中

的元素。一维数组元素的引用方式如下所示：

数组名 [下标];

在上述方式中，下标指的是数组元素的位置,数组元素的下标是从0开始的。例如，引用数组X的第3个元素的方式为X[2]为了帮助大家更好地理解数组元素的引用榜下业通计一个室例来演示，如下所示：

#include<stdio.h>
void main(int argc, char *argv[]){
    int x[5] = {2,3,1,4,6};
    int i;
    for (i = 0; i < 5; i++) {
        printf("%d\n", 2 * x[i]);
    }
}

注意！数组的下标都有一个范围,即“0~[数组长度-1]”，假设数组的长度为6，其下标范围为0~5。当访问数组中的元素时，下标不能超出这个范围，否则程序会报错。

 一维数组的常见操作

数组在编写程序时应用非常广泛，如经常需要对数组进行遍历、获取最值、排序等操作灵活地使用数组对实际开发很重要。接下来针对一维数组的常见操作进行详细的讲解，具体如下。

1、一维数组的遍历

在操作数组时，经常需要依次访问数组中的每个元素，这种操作称作数组的遍历。接下来使用for循环依次遍历数组中的元素，如下所示：

#include<stdio.h>
void main(int argc, char *argv[]){
    int x[5] = {2,3,1,4,6};
    int i = 0;
    for (i = 0; i < 5; i++) {
        printf("x[%d]:%d\n", i, x[i]);
    }
}

2、一维数组的最值

在操作数组时，经常需要获取数组中元素的最值。接下来通过案例演示如何获得数组中最大的数值。

#include<stdio.h>
int main(int argc, char *argv[]){
    int x[5] = {2,3,1,4,6};
    int nMax = x[0];
    int i = 0;
    for (i = 0; i < 5; i++) {
        if (x[i] > nMax) {
            nMax = x[i];
        }
    }
 
    printf("max:%d\n", nMax);
    return 0;
}

 在上面案例找那个实现了获取数组X最大值的功能。在第5行代码中假定数组中的第1个元素为最大值，并将其赋值给nMax，在第7~13行代码对数组中的其他元素进行遍历，如果发现比mMax值大的元素，就将最大值nMx设置为这个元素的值，这样，当数组遍历完成后,nMax中存储的就是数组中的最大值。

3、一维数组的排序

在操作数组时，经常需要对数组中的元素进行排序。接下来为大家介绍一种比较常见的排序算法一冒泡排序。在冒泡排序的过程中，不断地比较数组中相邻的两个元素，较小者向上浮、较大者往下沉，整个过程和水中气泡上升的原理相似，接下来，分步骤讲解冒泡排序的整个过程，具体如下。

第1步，从第1个元素开始，将相邻的两个元素依次进行比较，直到最后两个元素完成比较。如果前1个元素比后1个元素大，则交换它们的位置。整个过程完成后，数组中最后1个元素自然就是最大值，这样也就完成了第1轮的比较。

第2步，除了最后1个元素，将剩余的元素继续进行两两比较，过程与第1步相似，这样就可以将数组中第二大的数放在倒数第2个位置。

第3步，依次类推，持续对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较为止。

了解了冒泡排序的原理之后，接下来通过一个案例来实现冒泡排序。

#include<stdio.h>
void main(int argc, char ** argv[]){
    int arr[5] = { 9,8,3,5,2 };
    int temp = 0;
    int i, j;
    printf("冒泡排序前:\n");
    for (i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
 
    }
    printf("\n");
    for (i = 0; i < 5 - 1; i++) {
        for (j = 0; j < 5 - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    printf("冒泡排序后:\n");
    for (i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

 在上面的案例中，通过嵌套for循环实现了冒泡排序。其中，外层循环用来控制进行多少轮比较，每一轮比较都可以确定1个元素的位置，由于最后1个元素不需要进行比较，因此，外层循环的次数为数组的长度-1，内层循环的循环变量用于控制每轮比较的次数，在每次比较时,如果前者小于后者，就交换两个元素的位置。下面通过一张动图来演示冒泡排血的运算过程。

 

二维数组

二维数组的定义与初始化 

在实际的工作中，仅仅使用一维数组是远远不够的，例如，一个学习小组有5个人，每个人有3门课的考试成绩，如果使用一维数组解决是很麻烦的。这时，可以使用二维数组，维数组的定义方式与一维数组类似，其语法格式如下：

类型说明符 数组名[常量表达式1] [常量表达式2];

在上述语法格式中，“常量表达式1”被称为行下标，“常量表达式2”被称为列下标。

例如，定义一个3行4列的二维数组，具体如下：

int a[3][4];

在上述定义的二维数组中，共包含3*4个元素，即12个元素。

完成二维数组的定义后,需要对二维数组进行初始化,初始化二维数组的方式有4种，具体如下。

（1）按行给二维数组赋初值。例如:

int a[2][3] = {{1,2,3},{4,5,6}};

在上述代码中，等号后面有一对大括号，大括号中的第1对括号代表的是第1行的数组元素，第2对括号代表的是第2行的数组元素。

（2）将所有的数组元素按行顺序写在1个大括号内。例如

int a[2][3] = {1,2,3,4,5,6};

在上述代码中，二维数组a共有两行，每行有3个元素，其中，第1行的元素依次为1、2、3，第2行元素依次为4、5、6。

（3）对部分数组元素赋初值。例如：

int b[3][4] = {{1},{4,3},{2,1,2}};

在上述代码中,只为数组b中的部分元素进行了赋值，对于没有赋值的元素，系统会自动赋值为0

（4）如果对全部数组元素置初值，则二维数组的第1个下标可省略，但第2个下标不能省略。例如

int a[2][3] = {1,2,3,4,5,6};

可以写为

int a[][3] = {1,2,3,4,5,6};

系统会根据固定的列数，将后边的数值进行划分，自动将行数定为2。

二维数组的引用

二维数组的引用方式同一维数组的引用方式一样，也是通过数组名和下标的方式来引用数组元素，其语法格式如下：

数组名[下标] [下标];

在上述语法格式中，下标值应该在已定义的数组的大小范围内，例如，下面这种情况就是错误的。

int a[3][ 4];    //定义a为3行4列的二维数组
a[3][4]=3;    //对数组a第3行第4列元素赋值,出错
 
在上述代码中，数组a可用的行下标范围是0~2，列下标是0~3，a[3][4]超出了数组的下标范围。为了帮助读者更好地掌握二维数组的引用，接下来，通过一个案例来演示二维数组的遍历。
 
#include<stdio.h>
void main() {
    //申明并初始化数组
    int array[3][4] = { {1,2,3,4},{5,6,7,8},{9,10,11,12} };
    for (int i = 0; i < 3; i++)    //循环遍历
    {
        for (int j = 0; j < 4; j++)    //循环遍历
        {
            printf("[%d][%d]: %d", i, j, array[i][j]);
        }
        printf("\n");    //每行添加换行字符
    }
}

 当使用嵌套for循环遍历二维数组元素时，外层for循环用于变量数组的行元素，内层for循环用于遍历数组的列元素。从图中可以看出，程序依次将数组aray中的元素输出了。

二维数组的应用

熟悉了二维数组的定义和引用，接下来定义一个二维数组 StuScore[5][3]，用来存放5名同学3门课程的成绩，并定义变量m表示学生，n表示第几门成绩，aver表示每名同学3门课程的平均成绩，sum表示每名同学3门课的总成绩，具体如下案例所示：

#include<stdio.h>
void main(int argc, char *argv[])
{
    int StuScore[5][3] = {
        //张同学
        {88, 70, 90},
        //王同学
        {80, 80, 60},
        //李同学
        {89, 60, 85},
        //赵同学
        {80, 75, 78},
        //周同学
        {70, 80, 80}
    };
    int m = 0, n = 0;
    int nStuTotalScore = 0;
    int nMathTotalScore = 0;
    int nChineseTotalScore = 0;
    int nEnglishToatalScore = 0;
    printf("个人总成绩：\n");
    for (m = 0; m < 5; m++) {
        nStuTotalScore = 0;
        for (n = 0; n < 3; n++) {
            nStuTotalScore += StuScore[m][n];
            switch (n)
            {
            case 0:
                {
                    nMathTotalScore += StuScore[m][n];
                    break;
                }
                case 1:
                {
                    nChineseTotalScore += StuScore[m][1];
                    break;
                }
                case 2:
                {
                    nEnglishToatalScore += StuScore[m][2];
                }
            }
        }
        switch (m)
        {
            case 0:
            {
                printf("张同学：%d\n", nStuTotalScore);
                break;
            }
            case 1:
            {
                printf("王同学：%d\n", nStuTotalScore);
                break;
            }
            case 2:
            {
                printf("李同学：%d\n", nStuTotalScore);
                break;
            }
            case 3:
            {
                printf("赵同学：%d\n", nStuTotalScore);
                break;
            }
            case 4:
            {
                printf("周同学：%d\n", nStuTotalScore);
                break;
            }
        }
    }
    printf("小组数学总分： %d 小组数学平均分：%.2f\n",
        nMathTotalScore, (double)nMathTotalScore / 5);
    printf("小组语文学总分： %d 小组语文平均分：%.2f\n",
        nChineseTotalScore, (double)nChineseTotalScore / 5);
    printf("小组英语总分： %d 小组英语平均分：%.2f\n",
        nEnglishToatalScore, (double)nEnglishToatalScore / 5);
 
}

 上面案例中实现了计算小组各科平均分的功能。其中，第415行代码定义了一个二维数组，用来存储小组中每个成员的各科成绩。第25~45行代码通过遍历列下标获取每个小组不同学科的总分，第46~74行代码通过遍历行下标获取每个小组成员的总分，最后将小组不同学科的总分和平均分输出。

以上参考C语言中的一维数组和二维数组什么？怎么用？ - 知乎 (zhihu.com) 

例题——杨辉三角形

输入一个正整数n，打印出一个n行的杨辉三角形。n<=20。

若i==1，且j==1 ——> yh[1][1]=1（初始条件）

若i>=2，且j<=i——>yh[i][j]=yh[i-1][j-1]+yh[i-1][j]（递推方程）

 代码

#include<bits/stdc++.h>
using namespace std;
int tri[25][25], n;
int main(){
	cin>>n;
	tri[1][1] = 1;
	for(int i = 2; i <=n; i ++)
	    for(int j = 1; j <= i; j ++)
	        tri[i][j] = tri[i-1][j-1] + tri[i-1][j];
	for(int i = 1; i<=n; i ++){
	    for(int j = 1; j <=i-1; j ++)
	        cout<<tri[i][j]<<" ";
	    cout<<tri[i][i]<<endl;
	}
	return 0;
}

总结

好了，这次就到这里了，希望大家多多支持，记得点个不要钱的关注，谢谢大家Thanks♪(･ω･)ﾉ，拜拜