05-28 15:13 已编辑牛客_运营/测试

发布于北京

关注

数组

数组概述

数组是编程中最基础、最常用的数据结构之一，它可以存储一系列相同类型的数据元素。想象一下，如果你需要存储 100 个整数，难道要定义 100 个变量吗？这显然太麻烦了！数组就像一个有序的盒子，让你可以用一个变量名统一管理多个数据，并通过索引（下标）快速访问任意位置的元素。

数组的特点

连续存储：数组在内存中是连续存储的，这使得访问任意元素的速度非常快
固定大小：创建数组时需要指定其大小，且大小通常不可变（部分语言支持动态数组）
相同类型：数组中的所有元素必须是相同的数据类型
随机访问：可以通过索引直接访问任意位置的元素，时间复杂度为O(1)

数组的声明与初始化

不同编程语言中，数组的声明和初始化语法略有不同，下面分别介绍几种常见语言的用法。

C++

在 C++ 中，声明数组的基本语法如下：

数组内元素的数据类型 数组名[数组大小];

例如，如果我要声明一个包含 5 个整数的数组，数组名叫 a，可以这样写：

int a[5];
// 声明并初始化数组为特定值
int arr2[5] = {1, 2, 3, 4, 5};

关于数组的声明，有几个点需要特别注意：

数组的大小必须是一个非负常量表达式，不能是变量。
数组的大小在编译时就已经确定，不能在运行时改变。
定义在主函数以外的数组是全局数组，全局数组内元素的默认初始值全为默认值（数值类型为0，布尔类型为false，对象引用为null），且不占用主函数相对有限的内存空间。定义在主函数以内的数组是主函数内局部数组，局部数组内元素的默认初始值不一定全为默认值，且占用主函数相对有限的内存空间。一般情况下，笔者建议把数组定义在主函数以外。

Java

在 Java 中，声明数组的基本语法如下：

数组内元素的数据类型[] 数组名 = new 数组内元素的数据类型[数组大小];

例如，如果我要声明一个包含 5 个整数的数组，数组名叫 a，可以这样写：

int[] a = new int[5];
// 声明并初始化数组为特定值
int[] arr2 = {1, 2, 3, 4, 5};
// 或者
int[] arr3 = new int[]{1, 2, 3, 4, 5};

关于数组的声明，有几个点需要特别注意：

数组的大小可以是一个变量（与C++不同）。
数组是对象，存储在堆内存中。
未初始化的数组元素会被自动初始化为默认值（数值类型为0，布尔类型为false，对象引用为null）。
Java支持动态初始化，即可以先声明数组变量，稍后再初始化。

Python

在 Python 中，虽然没有原生的数组类型，但可以使用列表（list）或 numpy 数组来实现类似功能。基本语法如下：

# 使用列表作为数组
数组名 = [元素1, 元素2, ..., 元素n]

# 使用numpy数组（需要安装numpy库）
import numpy as np
数组名 = np.array([元素1, 元素2, ..., 元素n])

例如，如果我要创建一个包含5个整数的数组，可以这样写：

# 使用列表
arr1 = [1, 2, 3, 4, 5]

# 使用numpy
import numpy as np
arr2 = np.array([1, 2, 3, 4, 5])

如果数组元素很多，没有办法（或者懒得）一个一个把初始值列出来，也可以直接使用 * 运算符来快速生成一个包含相同元素的数组，这样就可以像 C++/Java 一样的思路来使用数组了！对应的语法为：

arr = [元素] * 数组大小

例如，如果我要创建一个包含5个整数的数组，数组名叫 a，可以这样写：

arr = [0] * 5

关于Python中的"数组"，有几个点需要特别注意：

列表(list)可以包含不同类型的元素，而numpy数组要求所有元素类型相同。
列表是Python内置类型，不需要额外安装；numpy数组需要安装numpy库(在终端运行 pip install numpy)。
列表的大小是动态的，可以随时添加或删除元素。
numpy数组支持向量化操作，性能更高。

数组的访问

数组中的元素通过索引（下标）来访问，索引从 0 开始计数。这意味着第一个元素的索引是 0，第二个元素的索引是 1，以此类推。

数组下标是从 0 开始计数的，依次是第 0 个，第 1 个，第 2 个...第 $n-1$ 个，而不是第 1 个，第 2 个...第 $n$ 个，这与我们日常生活中习惯的计数方法不同。在有些情况下，我们可以故意把数组开大一些，然后假装数组的第一个元素（即下标为 0 的元素）不存在，直接从下标为 1 的元素开始当作第一个元素用。这种写法在大部分情况下可以简化思维，同时减小越界错误的可能性，是笔者比较推荐的写法。

C++

C++ 中数组元素的访问语法如下：

数组名[索引];

下面是默认的以 0 为第一个下标的方式访问数组元素：

int arr[5] = {10, 20, 30, 40, 50};// 声明并初始化数组

// 访问数组元素
int firstElement = arr[0];  // 访问数组的第一个元素（10），并把对应值赋给变量firstElement
int thirdElement = arr[2];  // 访问数组的第三个元素（30），并把对应值赋给变量thirdElement

// 修改数组元素
arr[4] = 55;  // 访问数组的第五个元素（50），并将其修改为55

下面是默认的以 1 为第一个下标的方式访问数组元素：

int arr[10] = {0, 10, 20, 30, 40, 50};// 声明并初始化数组

// 访问数组元素
int firstElement = arr[1];  // 访问数组的第一个元素（10），并把对应值赋给变量firstElement
int thirdElement = arr[3];  // 访问数组的第三个元素（30），并把对应值赋给变量thirdElement

// 修改数组元素
arr[5] = 55;  // 访问数组的第五个元素（50），并将其修改为55

需要特别注意的是，如果你访问的下标超出了数组大小所规定的下标范围（比如下标小于0 或不小于数组大小），你的代码将会出现“未定义行为”，并且在运行时出错，导致程序返回值不为 0，这是一种非常危险的行为。

Java

Java 中数组元素的访问语法如下：

数组名[索引];

下面是默认的以 0 为第一个下标的方式访问数组元素：

int[] arr = {10, 20, 30, 40, 50}; // 声明并初始化数组

// 访问数组元素
int firstElement = arr[0];  // 访问数组的第一个元素（10），并把对应值赋给变量firstElement
int thirdElement = arr[2];  // 访问数组的第三个元素（30），并把对应值赋给变量thirdElement

// 修改数组元素
arr[4] = 55;  // 访问数组的第五个元素（50），并将其修改为55

下面是默认的以 1 为第一个下标的方式访问数组元素：

int[] arr = new int[10];
arr[1] = 10;
arr[2] = 20;
arr[3] = 30;
arr[4] = 40;
arr[5] = 50; // 声明并初始化数组

// 访问数组元素
int firstElement = arr[1];  // 访问数组的第一个元素（10），并把对应值赋给变量firstElement
int thirdElement = arr[3];  // 访问数组的第三个元素（30），并把对应值赋给变量thirdElement

// 修改数组元素
arr[5] = 55;  // 访问数组的第五个元素（50），并将其修改为55

需要特别注意的是，如果你访问的下标超出了数组大小所规定的下标范围（比如下标小于0 或不小于数组长度），你的代码将会抛出 ArrayIndexOutOfBoundsException 异常，这是一种运行时错误。

Python

Python 中数组元素的访问语法如下（以列表为例）：

数组名[索引]

下面是默认的以 0 为第一个下标的方式访问数组元素：

arr = [10, 20, 30, 40, 50]  # 声明并初始化数组

# 访问数组元素
first_element = arr[0]  # 访问数组的第一个元素（10），并把对应值赋给变量first_element
third_element = arr[2]  # 访问数组的第三个元素（30），并把对应值赋给变量third_element

# 修改数组元素
arr[4] = 55  # 访问数组的第五个元素（50），并将其修改为55

Python 还支持负数索引，表示从数组末尾开始计数：

last_element = arr[-1]  # 访问数组的最后一个元素
second_last = arr[-2]  # 访问数组的倒数第二个元素

下面是默认的以 1 为第一个下标的方式访问数组元素：

arr = [None] * 10  # 创建长度为10的数组
arr[1] = 10
arr[2] = 20
arr[3] = 30
arr[4] = 40
arr[5] = 50  # 声明并初始化数组

# 访问数组元素
first_element = arr[1]  # 访问数组的第一个元素（10）
third_element = arr[3]  # 访问数组的第三个元素（30）

# 修改数组元素
arr[5] = 55  # 访问数组的第五个元素（50），并将其修改为55

需要特别注意的是，如果你访问的下标超出了数组大小所规定的下标范围（比如下标小于负的数组长度或不小于数组长度），Python 会抛出 IndexError 异常，这是一种运行时错误。

数组的遍历

遍历数组是指按顺序访问数组中的每个元素。有多种方法可以遍历数组：

通过 for 循环遍历数组下标，通过依次访问数组对应下标的元素从而遍历数组。
通过拓展 for 循环直接对数组进行遍历（部分语言不支持）。

cpp
java
python

int arr[5] = {10, 20, 30, 40, 50};

// 使用 for 循环遍历下标
for (int i = 0; i < 5; i++) {
    cout << arr[i] << " ";
}
// 输出: 10 20 30 40 50

// C++11 后支持的范围for循环直接对数组进行遍历
for (int x : arr) {
    cout << x << " ";
}
// 输出: 10 20 30 40 50

int[] arr = {10, 20, 30, 40, 50};

// 1. 基本for循环遍历
// 通过索引访问每个元素
for (int i = 0; i < 5; i++) {
    System.out.print(arr[i] + " ");
}
// 输出: 10 20 30 40 50

// 2. 增强for循环（for-each）
// 直接访问元素值，不需要索引
for (int x : arr) {
    System.out.print(x + " ");
}
// 输出: 10 20 30 40 50

arr = [10, 20, 30, 40, 50]

# 1. 直接遍历元素
# 最简单的方式，不需要索引
for item in arr:
    print(item, end=" ")
# 输出: 10 20 30 40 50

# 2. 通过索引遍历
# 需要时可以使用索引
for i in range(5):
    print(arr[i], end=" ")
# 输出: 10 20 30 40 50

# 3. 使用enumerate同时获取索引和值
# 需要索引和值时最方便
for index, value in enumerate(arr):
    print(f"arr[{index}] = {value}")
# 输出:
# arr[0] = 10
# arr[1] = 20
# ...

例题 1：牛牛学数列6

题意

有一个数列，满足：

\begin{cases} a_1 = 0 \\ a_2 = 1 \\ a_3 = 1 \\ a_i = a_{i-1} + 2\cdot a_{i-2} + a_{i-3} (i \ge 4) \end{cases}

输入一个正整数 $n$ ，求数组的第 n 项，即 $a_n$ 。

思路

我们可以建立一个数组，先把前三项赋好初始值，然后从第四项开始，依次使用递推式计算出当前项的值，只到第 n 项为止。

代码实现

c++
java
python

#include<bits/stdc++.h>
using namespace std;
int a[40]; // 定义全局数组，存储数列各项值
//注意，这里故意把数组开大了一倍，这样我们就可以假装数组的第一个元素为 a[1] 了

int main() {
    int n; // 定义变量n，存储项数
    cin >> n; // 读取输入的n值
    
    // 初始化数列的前三项
    a[1] = 0; // 第一项为0
    a[2] = 1; // 第二项为1
    a[3] = 1; // 第三项为1
    
    // 从第4项开始，使用递推公式计算每一项的值
    for (int i = 4;i <= n; i++) {
        a[i] = a[i - 1]+2 * a[i - 2] + a[i - 3]; // 递推公式：a_i = a_{i-1} + 2*a_{i-2} + a_{i-3}
    }
    
    cout << a[n]; // 输出第n项的值
    return 0; // 程序正常结束
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取输入的n值
        int[] a = new int[40]; // 创建数组存储数列各项值
        
        // 初始化数列的前三项
        a[1] = 0; // 第一项为0
        a[2] = 1; // 第二项为1
        a[3] = 1; // 第三项为1
        
        // 从第4项开始，使用递推公式计算每一项的值
        for (int i = 4; i <= n; i++) {
            a[i] = a[i - 1] + 2 * a[i - 2] + a[i - 3]; // 递推公式
        }
        
        System.out.println(a[n]); // 输出第n项的值
    }
}

n = int(input()) # 读取用户输入的n值
a = [0] * 40 # 创建列表存储数列各项值

# 初始化数列的前三项
a[1] = 0 # 第一项为0
a[2] = 1 # 第二项为1
a[3] = 1 # 第三项为1

# 从第4项开始，使用递推公式计算每一项的值
for i in range(4, n+1):
    a[i] = a[i-1] + 2*a[i-2] + a[i-3] # 递推公式

print(a[n]) # 输出第n项的值

多维数组

在一维数组中，我们通过唯一的一个下标来获取对应位置的元素，这像是一个数轴的非负半轴，我们只要知道一个维度的下标就可以访问到对应位置的值。

二维数组就像一个二维的平面，我们只有知道了”横坐标“和”纵坐标“这两个下标，才能唯一确定一个在二维数组中的位置。实际上，二维数组更像一个矩阵，或者说是一个只有”非负整数点“的离散的平面。

\begin{equation} \left[ \begin{array}{cccc} a_{11}& a_{12} &\cdots & a_{1m}\\ a_{21}& a_{22} &\cdots& a_{2m}\\ \vdots & \vdots & \ddots & \vdots \\ a_{n1}& a_{n2} &\cdots &a_{nm} \end{array} \right ] \end{equation}

由一维数组构成的数组是二维数组，由二维数组构成的数组是三维数组，由三维数组构成的数组是三位数组......

这样的维度还可以无限向上叠加，不过道理都是一样的，无非是在数组名后面多加几个中括号，多填几个参数的事。接下来，我们就以二维数组为例，介绍一下二维数组的用法。

二维数组的声明与初始化

这一部分的语法与一维数组基本一致，唯一的不同就是多了一个维度的中括号需要填数。

cpp
java
python

// 声明一个3行4列的二维数组
int matrix[3][4];

// 声明并初始化
int matrix2[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// 部分初始化，未指定的元素默认为0
int matrix3[3][4] = {
    {1, 2},
    {5},
    {9, 10, 11}
};

// 声明一个3行4列的二维数组
int[][] matrix = new int[3][4];

// 声明并初始化
int[][] matrix2 = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// Java支持不规则数组（每行长度可以不同）
int[][] irregular = {
    {1, 2, 3},
    {4, 5},
    {6, 7, 8, 9}
};

# 使用嵌套列表创建二维数组
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

二维数组的访问与遍历

访问二维数组第 $i$ 行第 $j$ 列的元素的语法为：

数组名[i][j];

在我们访问二维数组的各个元素时，我们经常会搞混一件事：到底哪个中括号里面填行，哪个填列？一般情况下，我们约定：

从左往右第一个维度为行，第二个维度为列。
遍历数组时往往先从上到下遍历行，后从左往右遍历对应行的每一列。
由于我们之前约定过第一层循环一般用 i，第二层用 j，以此类推，你可以把 i 和行数、j 和列数直接联系起来

代码实现

cpp
java
python

int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// 访问元素
int element = matrix[1][2];  // 值为7（第2行第3列）

// 修改元素
matrix[0][0] = 100;

// 使用嵌套for循环遍历
for (int i = 0; i < 3; i++) { //枚举行数 i
    for (int j = 0; j < 4; j++) {  // 枚举列数 j
        cout << matrix[i][j] << " ";
    }
    cout << endl;
}

int[][] matrix = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// 访问元素
int element = matrix[1][2];  // 值为7（第2行第3列）

// 修改元素
matrix[0][0] = 100;

// 使用嵌套for循环遍历
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[i].length; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

// 使用增强for循环遍历
for (int[] row : matrix) {
    for (int value : row) {
        System.out.print(value + " ");
    }
    System.out.println();
}

matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

# 访问元素
element = matrix[1][2]  # 值为7（第2行第3列）

# 修改元素
matrix[0][0] = 100

# 使用嵌套for循环遍历
for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        print(matrix[i][j], end=" ")
    print()

# 使用增强for循环遍历
for row in matrix:
    for value in row:
        print(value, end=" ")
    print()
# 注意，在你默认 a[1][1] 为第一个元素时，我们只是假装下标为0的元素不存在，
# 使用增强for循环时仍然会把它访问到

时空复杂度

空间复杂度

如何预测程序需要消耗的内存空间呢？

在基本数据类型中，我们已经列出了各个基本数据类型单个变量所占用的内存的大小，只要统计我们代码中各个变量占用的内存之和，即可得到大致的程序需要消耗的空间（忽略程序运行带来的其他空间开销）。

不难发现，大多数变量占用的内存大小都微乎其微，相比之下，数组等能容纳大量变量的数据结构就显得举足轻重了。对于大部分题目而言，题目允许使用的空间只有 $256$ MB,我们可以先计算一下自己代码所占用的空间，进而判断我们的代码能否满足题目的空间需求。

例如我们创建一个大小为 $n$ 的数组，数组内每个元素占用的空间为 $4$ B，则这个数组占用的空间为 $4n$ B。

比如当数组大小为 $10^6$ 时，数组占用的空间为 $4 \cdot 10^6$ B，即 $\frac{4 \cdot 10^6}{1024 \cdot 1024}$ MB，约为 $3.81$ MB。

然而，在有些时候，我们可以忽略掉数组中各个变量占用的空间，这样就可以得到一个可以大致估计程序占用空间的表达式，我们用 O(表达式) 来表示这个空间开销，这就是空间复杂度。以创建一个大小为 $n$ 的数组为例，此时的空间复杂度为 $O(n)$ 。

时间复杂度

在计算机科学中，时间复杂度和空间复杂度是衡量算法性能的重要指标。它们描述了算法在执行过程中所需的时间和空间资源的增长情况。

我们如何才能判断计算机执行我们的代码需要多少时间呢？现代计算机在一秒内大概能执行一亿 ( $10^8$ ) 个 C++ 指令或一千万 ( $10^7$ ) 个 Java 或 Python 指令，如果我们能估计出自己的代码大概包含的指令数量，我们就可以大致估计出我们的代码需要执行的时间，不难推导出其公式为：

代码运行时间 = \frac{您选择的语言在代码中的指令数量}{对应语言一秒内能执行的指令数量} 秒

那么，如何估计我们的代码大概包含的指令数量呢？

在不考虑循环语句时，我们发现一行代码差不多就相当与一个指令，因此我们可以直接统计代码的行数来估计指令数量。

但是，如果代码中出现了循环，我们便会发现，循环体内的代码会被循环执行多次。比如果我们如果循环 $1000$ 次输出 Hello Nowcoder，那么这个循环就相当于 $1000$ 条指令。同理，如果我们循环 $n$ 次输出 Hello Nowcoder，那么这个循环就相当于 $n$ 条指令。

接下来，我们看下面这一段 C++ 代码，尝试分析一下这段代码的指令数量：

#include<bits/stdc++.h>     //只被执行一次
using namespace std;        //只被执行一次
int a[200000];              //只被执行一次
int main(){                 //只被执行一次
    int n;                  //只被执行一次
    int m=0;                //只被执行一次
    cin>>n;                 //只被执行一次
    for(int i=1;i<=n;i++){  //只被执行一次
        cin>>a[i];          //大括号内的代码会被循环执行 n 次
        m+=a[i];            //大括号内的代码会被循环执行 n 次
    }                       //只被执行一次
    cout<<m;                //只被执行一次
    return 0;               //只被执行一次
}                           //只被执行一次

不难统计出，只会被执行一行的代码有 $12$ 行代码，此外，还有 $2$ 行代码会被循环执行 $n$ 次，因此，这段代码的指令数量为：

2n + 12

然而，我们也发现，统计出具体的大概的指令数量时十分繁琐的，但同时，在 $n$ 不断变大的过程中， $n$ 前面的系数 $2$ 、 $n$ 后面加的常数项 $+12$ 对表达式的值，相比于 $n$ 的变大，都显得微乎其微。

此时我们便提出了一个新的概念：时间复杂度。简单来说，时间复杂度就是代码的指令数量，忽略掉其中关键变量的系数与低次项后的结果，一般用 O(表达式) 表达。

比如刚才的那个表达式，我们忽略掉 $n$ 前面的系数 $2$ 、 $n$ 后面加的常数项 $+12$ 后，最终得到的时间复杂度为：O(n)。

接下来，我们再看一道例题，并尝试分析一下这道题目的时空复杂度。

例题 2：二维斐波那契数列

题意

有一个数列，满足：

\begin{cases} a_{1,1} = 1 \\ a_{i,1} = a_{i-1,1} (i \ge 2) \\ a_{1,i} = a_{1,i-1} (i \ge 2) \\ a_{i,j} = a_{i-1,j} + a_{i,j-1} (i,j \ge 2) \end{cases}

输入两个正整数 $n,m$ ，求 $a_{n,m}$ 的值。

思路

我们可以建立一个数组，先把 $a_{1,1}$ 赋好初始值，然后遍历行数和列数的所有可能取值，使用对应的递推式获取对应行和列位置二维数组的值即可。

注意到，如果我们提前把行或列中有一个为 0 的情况赋值为 0，则可以把中间两个递推式转化为第四个递推式（加 0 等于没加），这样我们就可以极大程度的简化我们的代码。

为了方便和数学递推式一一对应，在参考代码中，我们并没有使用这个优化，而是直接把所有情况都列出来了。

代码实现

c++
java
python

#include<bits/stdc++.h>
using namespace std;
int a[40][40]; // 定义全局数组，存储数列各项值
//注意，这里故意把数组开大了一倍，这样我们就可以假装数组的第一个元素为 a[1] 了

int main(){
    int n,m; // 定义变量n和m，分别表示二维数组的行数和列数
    cin>>n>>m; // 读取输入的行数n和列数m
    
    // 使用递推公式计算每一项的值
    for(int i=1;i<=n;i++){ // 遍历每一行
        for(int j=1;j<=m;j++){ // 遍历每一列
            if(i==1&&j==1) a[i][j]=1; // 递推式1：第一行第一列的值为1
            else if(i==1) a[i][j]=a[i][j-1]; // 递推式2：第一行的值等于左边相邻的值
            else if(j==1) a[i][j]=a[i-1][j]; // 递推式3：第一列的值等于上方相邻的值
            else a[i][j]=a[i-1][j]+a[i][j-1]; // 递推式4：其他位置的值等于上方值加左边值
        }
    }
    
    cout<<a[n][m]; // 输出二维数组第n行第m列的值
    return 0; // 程序正常结束
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取行数n
        int m = scanner.nextInt(); // 读取列数m
        int[][] a = new int[40][40]; // 创建二维数组存储数列值
        
        // 使用递推公式计算每一项的值
        for(int i=1; i<=n; i++) { // 遍历每一行
            for(int j=1; j<=m; j++) { // 遍历每一列
                if(i==1 && j==1) a[i][j] = 1; // 递推式1
                else if(i==1) a[i][j] = a[i][j-1]; // 递推式2
                else if(j==1) a[i][j] = a[i-1][j]; // 递推式3
                else a[i][j] = a[i-1][j] + a[i][j-1]; // 递推式4
            }
        }
        
        System.out.println(a[n][m]); // 输出结果
    }
}

n, m = map(int, input().split()) # 读取行数n和列数m
a = [[0] * 40 for _ in range(40)] # 初始化二维数组

# 使用递推公式计算每一项的值
for i in range(1, n+1): # 遍历每一行
    for j in range(1, m+1): # 遍历每一列
        if i == 1 and j == 1:
            a[i][j] = 1 # 递推式1
        elif i == 1:
            a[i][j] = a[i][j-1] # 递推式2
        elif j == 1:
            a[i][j] = a[i-1][j] # 递推式3
        else:
            a[i][j] = a[i-1][j] + a[i][j-1] # 递推式4

print(a[n][m]) # 输出结果

时空复杂度分析

在本题中，我们定义的数组中的元素有 $n$ 行、 $m$ 列，一共有 $n \cdot m$ 个元素，所以最终的空间复杂度为 $O(n \cdot m)$ 。

在本题中，我们的代码有两层循环，第一层循环遍历了可能的每一行，一共循环了 $n$ 次。对于每一行，我们循环遍历了对应行的每一列，一共循环了 $m$ 次。在对于两层循环内部的代码，会被执行 $n \cdot m$ 次，所以最终的时间复杂度为 $O(n \cdot m)$ 。

数组的优缺点（了解即可）

在编程中使用数组时，了解其优缺点非常重要，这有助于我们在不同场景下做出合理的选择。下面详细分析数组的优缺点及其适用场景。

优点

访问速度快：通过索引可以直接访问数组内任意元素
- 这是数组最显著的优势，特别适合需要频繁随机访问的场景
内存效率高：连续存储，没有额外的结构开销
- 不需要存储指针或链接信息，节省内存空间
缓存友好：连续内存布局有利于 CPU 缓存
- 现代 CPU 的缓存预取机制能更好地利用数组的连续内存特性
实现简单：容易理解和使用
- 语法简单直观，学习曲线平缓

缺点

虽然数组有很多优点，但它也存在一些局限性：

大小固定：创建后大小通常不可变（除非使用动态数组）
- 这意味着在创建数组时必须预先知道所需的最大空间
插入和删除效率低：在数组中间插入或删除元素需要移动其他元素
- 如果在数组中间插入或删除一个元素，插入或删除元素的位置后面所有元素的位置都需要改变，这会导致大量元素的移动，消耗的时间较长。
空间浪费：如果预分配的空间过大，可能造成内存浪费
- 实际使用空间远小于分配空间时，剩余空间无法被其他用途使用
类型单一：只能存储相同类型的元素
- 限制了数据结构的灵活性