数据结构与算法（八）——栈思想下的算法题目解析
一、括号匹配检验
1，题目
假设表达式中允许包含两种括号：圆括号与方括号，其嵌套顺序随意，即([]())或者[([][])]都是正确的，而[(]或者(()])或者([())都是不正确的格式。请设计一个算法来检验括号是否正确匹配。
2，题目分析
这个题目中，是要检验一段字符串当中的括号能否正常匹配，凡是有前后“匹配”意味的题目，都可以尝试着使用栈思想来解决。
根据题目字眼，我可以确定，字符串当中只会有四个字符，它们分别是：()[]。
字符串本质上就是字符数组（二者的唯一区别是字符串比字符数组多了一个结束符\0），因此我们可以依次遍历字符串中的每一个字符，然后与当前处于栈顶的节点值进行匹配。如果匹配成功则出栈，如果匹配不成功则入栈。最后查看是否空栈，如果空栈则说明完全匹配，否则为匹配不成功。
如上图所示，先将1号位上的元素入栈，然后从第2号位开始遍历接下来的字符。
遍历到2号位，发现与1号位不匹配，则入栈。
3号位与2号位不匹配，入栈。
4号位与3号位匹配，出栈。
5号位与2号位不匹配，入栈。
6号位与5号位匹配，出栈。
7号位与2号位匹配，出栈。
8号位与1号位匹配，出栈。
这样的话，如果完全匹配的话，最后的栈内是没有元素的。如果站内有元素，则说明有未匹配上的。
3，代码分析
栈结构的实现代码如下：
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
#include <string.h>
// 栈操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 栈结构的初始容量
#define Max_Size 100
// 顺序栈结构
typedef struct {
char datas[Max_Size];
int top; // 栈顶
} SequentialStack;
// 栈的初始化
Status initSequentialStack(SequentialStack *stack) {
stack->top = -1;
return Success;
}
// 入栈
Status addElement(SequentialStack *stack, char element) {
// 栈不存在，则返回错误
if (!stack) {
return Error;
}
// 满栈，也返回错误
if (stack->top + 1 == Max_Size) {
return Error;
}
// 入栈
stack->datas[++stack->top] = element;
return Success;
}
// 出栈
Status removeElement(SequentialStack *stack) {
// 栈不存在则返回错误
if (!stack) {
return Error;
}
// 空栈则返回错误
if (stack->top == -1) {
return Error;
}
// 出栈
stack->top--;
return Success;
}
// 获取栈顶元素
Status getTopElement(SequentialStack stack, char *topElement) {
// 空栈
if (stack.top == -1) {
return Error;
}
*topElement = stack.datas[stack.top];
return Success;
}我们这里使用的是一个顺序栈。我们这里的这个算法问题，是使用栈的思想去解决问题，至于具体是使用顺序栈还是使用链式栈，其实都可以。不管是顺序栈，还是链式栈，他们只是实现栈的思想的途径，如果没有啥特殊的要求，使用他俩哪一个都是可以的。
二者的不同点在于：
1，顺序栈在出栈的时候，不会将对应的元素在内存中删掉
2，链式栈在出栈的时候，会将对应的元素在内存中销毁
检验字符串是否匹配的算法如下：
// 校验字符串是否匹配
bool checkString(char *str) {
long strLength = strlen(str); // 字符串长度
// 当字符串为空的时候，直接返回true
if (strLength == 0) {
return true;
}
// 新建一个顺序栈
SequentialStack stack;
initSequentialStack(&stack);
// 先将字符串的第一个字符入栈
addElement(&stack, str[0]);
// 从字符串的第2个字符开始循环遍历
char topElement;
for (int i = 1; i < strLength; i++) {
// 获取到当前遍历到的字符
char currentChar = str[i];
// 将当前字符与当前的栈顶元素进行匹配，匹配到则出栈，匹配不到则入栈
getTopElement(stack, &topElement);
switch (topElement) {
case '[':
if (currentChar == ']') {
removeElement(&stack);
} else {
addElement(&stack, currentChar);
}
break;
case '(':
if (currentChar == ')') {
removeElement(&stack);
} else {
addElement(&stack, currentChar);
}
break;
default:
return false;
break;
}
}
// 遍历完了之后查看是否为空栈，如果是空栈则说明完全匹配，否则就是不匹配
return stack.top == -1;
}验证代码如下：
int main(int argc, const char * argv[]) {
char str[Max_Size];
printf("请输入:\n");
scanf("%s", str);
printf("当前字符串是:%s\n", str);
printf("是否匹配:%d\n", checkString(str));
return 0;
}二、数制的转换
1，题目
请设计一个算法，将十进制转换成八进制。
2，题目分析
（1）通过一个临时变量temp记录原十进制数字
（2）令temp对8取余，然后将余数入栈
（3）令temp除以8，并赋值为temp
（4）循环执行步骤2、3，直到temp为0为止
（5）遍历打印栈中元素即为八进制结果
3，代码分析
先来看一下栈结构的代码：
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
#include <string.h>
#define Max_Size 10 // 栈的最大承载量
// 操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 栈中元素类型
typedef int ElementType;
// 顺序栈结构
typedef struct SequentialStack {
int top; // 栈顶
ElementType datas[Max_Size];
} SequentialStack;
// 初始化一个空栈
Status initSequentialStack(SequentialStack *stack) {
stack->top = -1;
return Success;
}
// 入栈
Status push(SequentialStack *stack, ElementType element) {
if (!stack) {
return Error;
}
if (stack->top == Max_Size - 1) {
return Error;
}
stack->datas[++stack->top] = element;
return Success;
}
// 打印顺序栈
Status printStack(SequentialStack stack) {
int top = stack.top;
if (top == -1) {
printf("空栈\n");
return Success;
}
printf("栈的内容（自顶到底）：\n");
while (top >= 0) {
printf("%d\n", stack.datas[top--]);
}
return Success;
}我这里采用了顺序栈的结构。
接着来看题目的解答：
void convertDecimalToOctal(int decimalNum) {
int originalNum = decimalNum;
SequentialStack stack;
initSequentialStack(&stack);
int remainder;
while (originalNum > 0) {
// 首先取余，然后将余数入栈
remainder = originalNum%8;
push(&stack, remainder);
// 将原数字缩小8倍
originalNum = originalNum/8;
}
printStack(stack);
}验证代码如下：
int main(int argc, const char * argv[]) {
convertDecimalToOctal(16);
return 0;
}三、每日气温
1，题目
根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置0来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
2，解法一——暴力求解
思路如下：
（1）新建一个数组array，用于记录还需要多少天超过当前温度
（2）最后一个气温没法比较，直接设置为0
（3）依次遍历原来的气温数组temperatures中的元素，假设当前遍历到的下标为i，则在当前遍历体中再从i+1位置进行二次遍历，在二次遍历中查找比当前温度高的那个元素，找到后将该元素下标与i的差值插入到array中；如果在第二层遍历中没有找到对应的元素，则将0插入到array中
（4）有一个特殊的情况需要注意一下，就是当在上述第一层遍历的时候，如果发现当前温度与上一个温度相等，那么就将上一个温度位置上的气温天数减1即可。如果此时上一个温度位置上的气温天数是0，那么这个位置上的气温天数也就直接设置为0
代码如下：
int * solveByForce(int *temperatures, int arrayLength) {
// 开辟一个数组用于记录结果
int *array = malloc(sizeof(int) * arrayLength);
// 最后一位直接设置为0
array[arrayLength - 1] = 0;
// 两层遍历求出各个位置上的结果
for (int i = 0; i < arrayLength; i++) {
int currentTemperature = temperatures[i];
// 如果当前遍历到的气温与数组中上一个气温相等，则直接令上一个气温的结果减去1即可，无需再走下面的循环
if (i > 0 && currentTemperature == temperatures[i-1]) {
array[i] = array[i-1] > 0 ? array[i-1] - 1 : 0;
continue;
}
// 寻找接下来大于当前温度的温度
for (int j = i + 1; j < arrayLength; j++) {
int tempTemperature = temperatures[j];
if (tempTemperature > currentTemperature) {
array[i] = j - i;
break;
}
array[i] = 0;
}
}
return array;
}2，解法二——跳跃对比法
思路如下：
（1）跳跃对比法实际上是在暴力求解上的一个优化。
（2）跳跃对比法同样是两层遍历，只不过暴力求解法的第一层遍历是从前往后，而跳跃对比法的第一层遍历是从后往前。
（3）与暴力求解一样，结果数组的最后一位直接设置为0
（4）在第一层遍历的时候，当前遍历到的气温是temperature，然后进行第二层遍历，第二层遍历自第一层遍历体中的i+1开始，一直遍历到最后
（5）第二层遍历的时候，不是一个一个逐个的遍历，而是跳跃遍历。比如，一开始第二层遍历中的temperature2<当前第一层遍历中的temperature，那么接下来的j不是+1，而是+array[j]，也就是说，跳跃到比这个数更大的那个数上面去，这样就可以大大减少循环的次数。
（6）如果说在第二层循环中找到了大于temperature的温度，那么将底标差值插入到array[i]即可，如果没有找到则array[i]=0。
代码如下：
int * solveByJump(int *temperatures, int temperaturesCount) {
// 新建一个结果数组
int *resultArray = malloc(sizeof(int) * temperaturesCount);
// 直接将结果数组的最后一个元素赋值为0
resultArray[temperaturesCount - 1] = 0;
// 自右往左倒序遍历
for (int i = temperaturesCount - 2; i >= 0; i--) {
int currentTemperature = temperatures[i];
// 给当前的位置赋一个初始值
resultArray[i] = 0;
// 二层跳跃遍历，找寻更高的温度，找到的话就更新该位置的结果
for (int j = i + 1; j < temperaturesCount; j+=resultArray[j]) {
int tempTemperature = temperatures[j];
// 如果能够找到比当前温度高的温度，那么就写入结果
if (tempTemperature > currentTemperature) {
resultArray[i] = j - i;
break;
}
// 如果后面没有更高的温度了，那么就直接跳出本次二层循环
if (resultArray[j] == 0) {
break;
}
}
}
return resultArray;
}3，解法三——栈思想求解
思路如下：
（1）创建一个结果数组resultArray，用于记录对应位置上的温度被超过还需要多少天；创建一个栈stackArray（以数组形式存在），用于记录暂时还未找到超越温度的温度的下标。
（2）从第一个元素开始循环遍历temperatures数组的每一个元素，当前遍历到的元素是currentTemperature，其坐标是i
①如果stackArray为空，则直接将currentTemperature的底标i入栈；
②如果stackArray不为空，则取出其栈顶j，然后获取到对应的温度temp=temeratures[j]，将temp与currentTemperature进行比较。如果currentTemperature>temp，则resultArray[j] = i - j，并且将当前栈顶出栈，然后继续上述遍历stackArray的操作；否则，将temp的下标入栈，并进入下一层遍历。
（3）上述第二步完成之后，此时stackArray中的元素就是尚未找到比他们高的温度的元素坐标，此时遍历stackArray取出每一个index，然后将result数组的index坐标下的值都设为0即可。
（4）栈思想求解的核心就是，栈中存储的是当前遍历到的温度的位置之前的没有找到较大温度的位置，而栈顶中保存的位置上的温度势必小于等于栈顶下面保存的位置上的温度，所以对于每一次遍历到的温度，需要查看是否大于栈顶的温度，如果大于则对栈顶保存的位置进行结果赋值，然后将当前栈顶出栈并继续判断新的栈顶，直到不大于栈顶位置上的温度为止。需要注意的是，每一次遍历快结束的时候都需要将当前遍历到的位置压栈，因为当前遍历到的位置上的温度并没有去查找较高温度。
（5）我们这里是通过一个数组来实现的栈结构，我们这里使用的是栈思想，至于怎么实现，可以使用顺序存储，可以使用链式存储，也可以直接使用数组。
代码如下：
int * solveByStack(int *tempetures, int totalCount) {
// 用于记录超过对应位置上的温度还需要多少天
int *resultArray = malloc(sizeof(int) * totalCount);
// 新建一个栈，用于记录尚未找到较高温度的元素的坐标
int *stackArray = malloc(sizeof(int) * totalCount);
int top = -1; // 栈顶指针
// 依次遍历tempetures数组中的每一个元素
for (int i = 0; i < totalCount; i++) {
// 获取到当前的温度
int currentTemerature = tempetures[i];
// 如果栈stackArray为空，那么将当前温度的下标直接入栈
if (top == -1) {
stackArray[++top] = i;
continue;
}
// 如果栈stackArray不为空，遍历栈
while (top > -1) {
// 获取栈顶保存位置上的温度
int j = stackArray[top]; // 栈顶保存的下标
int temp = tempetures[j]; // 栈顶保存的下标所对应的温度
// 如果当前遍历到的温度大于栈顶温度，则当前栈顶所保存的位置就找到了结果
if (temp < currentTemerature) {
// 保存结果
resultArray[j] = i - j;
// 出栈
top--;
continue;
}
// 如果当前遍历到的温度不大于栈顶温度，则跳出当前while循环
break;
}
// 将当前遍历到的位置入栈
stackArray[++top] = i;
}
// 如果栈中还有元素，那么就说明这些位置上的气温没有找到较高的温度了，所以此时要将这些位置上的结果都设置为0
while (top > -1) {
resultArray[stackArray[top--]] = 0;
}
return resultArray;
}四、字符串编码
1，题目
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
例如:
s = "3[a]2[bc]", 返回 "aaabcbc".z
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
2，思路
以 12[a] 为例进行分析。
（1）新建一个栈结构stack，遍历原字符串中的每一个字符c，如果c!=']'，则依次入栈；否则执行（2）
（2）首先找到需要复制的字符段，找到之后通过一个临时栈进行保存
（3）然后找到需要复制的次数，找到之后将其转换成int类型
（4）循环复制，将内容插入到stack栈中
3，代码分析
char *decodeString(char *originalStr) {
long strLength = strlen(originalStr); // 原字符串长度
// 1，新建一个栈，用于承载遍历到的字符
int stackSize = 50; // 默认先设置为50，后面不够了可以扩容
char *stack = malloc(sizeof(char) * stackSize);
int stackTop = -1; // 栈顶
// 2，遍历原字符串中的每一个字符
for (int i = 0; i < strLength; i++) {
char currentChar = originalStr[i]; // 当前遍历到的字符
// 2.1，如果当前遍历到的字符不是]，则入栈
if (currentChar != ']') {
// 2.1.1，如果栈顶抵达栈的上限，则为栈扩容
if (stackTop == stackSize - 1) {
stack = realloc(stack, (stackSize += 50) * sizeof(int));
}
// 2.1.2 将当前遍历到的字符入栈
stack[++stackTop] = currentChar;
continue;;
}
// 2.2，如果当前遍历到的字符是]
/* 2.2.1，找寻当前需要复制的那些字符 */
// 新建一个临时的栈结构，用于存储本次应该复制的字符
int tempStackSize = 20; // 临时栈的大小默认设置为20，后面可以扩容
char *tempStack = malloc(sizeof(char) * tempStackSize);
int tempStackTop = -1;
while (stackTop > -1 && stack[stackTop] != '[') {
// 在必要的时候进行扩容
if (tempStackTop == tempStackSize - 1) {
tempStack = realloc(tempStack, (tempStackSize += 20) * sizeof(int));
}
// 对需要复制的字符进行入栈
tempStack[++tempStackTop] = stack[stackTop--];
}
/* 2.2.2，找寻当前的这些字符需要复制多少遍 */
// 复制遍数的尾端
int countTailIndex = --stackTop; // 首先将[字符出栈，然后再获取最新的栈顶
// 复制遍数的首端
int countHeadIndex;
for (countHeadIndex = countTailIndex; countHeadIndex > -1 && stack[countHeadIndex] >= '0' && stack[countHeadIndex] <= '9'; countHeadIndex--);
countHeadIndex++;
// 将复制遍数拼接成字符串
char *countStr = malloc(sizeof(int) * 10);
while (stackTop >= countHeadIndex) {
// 将stack栈顶中的数字出栈，放到countStr的对应位置上
countStr[stackTop - countHeadIndex] = stack[stackTop];
stackTop--;
}
countStr[countTailIndex - countHeadIndex + 1] = '\0'; // 给字符串拼接结尾符
// 生成int类型的复制次数
int count = atoi(countStr);
/* 2.2.3，执行复制操作 */
for (int i = 0; i < count; i++) {
int aaa = tempStackTop;
while (aaa > -1) {
stack[++stackTop] = tempStack[aaa--];
}
}
// 复制完了之后销毁临时的栈
free(tempStack);
tempStack = NULL;
}
// 3，给字符串加上结束符号\0
char *finalResult = realloc(stack, (stackTop + 1) * sizeof(char)); // 多开辟一个字符的空间
finalResult[++stackTop] = '\0';
free(stack); // 销毁原来的stack
return finalResult;
}（1）本案例中涉及到了空间扩容的知识点，在C语言中，我们是通过realloc进行扩容的。
（2）在C语言中，字符串就是字符的数组，其类型就是char *。二者的不同点在于，字符串有结束符\0。
（3）本例中我们使用了栈思想来解决，我们这里使用的是字符串数组来实现的栈结构，这样比使用链式存储更方便。
五、去除重复字母
1，题目
给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）
示例1:
输入:"bcabc"
输出:"abc"
示例2:
输入:"cbacdcbc"
输出:"acdb"
2，题目分析
（1）仅包含小写字母，说明无大写、无特殊字符、无数字。
（2）题目要求返回结果的字典序最小，且不能打乱其他字符的相对位置。
那么什么是字典序呢？其实字符串之间的比较和数字之间的比较是不一样的，字符串的比较是从头往后挨个进行字符串的比较，俩字符串哪一个大取决于这俩字符串中第一个对应不相等的字符，比如apple的字典序小于book。
例如，bcabc，你应该返回abc，而不是bca、cab；
例如，cbacdcbc，你应该返回acdb，而不是cbad、bacd、adcb
例如，zab，你应该返回zab，而不是abz
3，解题思路
（1）判断字符串originalLetters可能出现的特殊情况，比如原字符串originalLetters为空、originalLetters只有一个字符的场景
（2）用一个letterCounts数组记录字符串中字母出现的次数，由于共有26个小写字母，所以给letterCounts开辟26个char大小的空间
（3）申请一个字符串栈stack（本质上就是一个字符数组），用来存储去除重复字母的结果，并利用它的特性帮助我们找到正确的次序
（4）遍历字符串originalLetters
（5）从0~top遍历stack，判断当前字符originalLetters[i]是否存在于栈stack中并将结果记录为isExist
（6）如果isExist==true，表示当前的stack已经有这个字符了，没有必要重复存储该字母，所以将originalLetters[i]在letterCounts中存储的出现次数减1，并继续遍历下一个字符。
（7）如果isExist==false，则需要将当前字符originalLetters[i]入栈，但是在入栈之前需要处理一下当前的栈顶元素，具体的操作如下：
自栈顶开始循环遍历当前的栈stack，如果当前的栈顶值大于当前字符originalLetters[i]，并且当前栈顶值在后面还会出现，那么就将当前栈顶出栈，循环遍历stack结束之后再将当前字符originalLetters[i]入栈
（8）直到遍历完所有字符后，则为字符串栈stack 添加一个结束符’\0’，并返回当前字符串首地址
4，代码分析
char *removeDuplicateLetters(char *originalLetters) {
// 1，处理特殊的场景
long lettersLength = strlen(originalLetters);
if (!originalLetters || lettersLength <= 1) { // 空串或者只有一个字符
return originalLetters;
}
// 2，新建一个数组letterCounts，用于记录原始字符串中26个小写字母分别出现的次数
int letterCounts[26] = {0};
// 3，新建一个栈结构，用于承载最终的结果
char *stack = malloc(sizeof(char) * 27); // 这里开辟的空间要比26多1位，目的是为了在最后加上字符串结束符\0
memset(stack, 0, sizeof(char) * 27); // 将栈stack的各元素空间填充为0
int stackTop = -1; // 栈顶指针
// 4，计算原始字符串中每个字符出现的次数
for (int i = 0; i < lettersLength; i++) {
letterCounts[originalLetters[i] - 'a']++;
}
// 5，遍历原始字符串中的每一个字符
for (int i = 0; i < lettersLength; i++) {
// 5.1，获取当前遍历到的字符
char currentChar = originalLetters[i];
// 5.2，判断当前字符是否已经在栈中出现过
bool isExist = false;
for (int i = 0; i < stackTop; i++) {
if (stack[i] == currentChar) {
isExist = true;
}
}
// 5.3，如果当前字符在栈中已经有了，那么栈中的那个相同的字符已经在合适的位置了，所以当前遍历到的这个字符的出现次数直接减1即可
if (isExist) {
letterCounts[currentChar - 'a']--;
continue;
}
// 5.4，如果当前的字符在栈中没有存在，那么就需要将当前的字符入栈，但是在入栈之前需要先将栈中的不符合当前条件的元素给出栈。
// 5.4.1，如果栈顶元素大于当前遍历到的字符，并且该栈顶元素在后面还会出现，那么就需要出栈
while (stackTop > -1 && stack[stackTop] > currentChar && letterCounts[stack[stackTop] - 'a'] > 1) {
letterCounts[stack[stackTop] - 'a']--; // 栈顶字母出栈之后，后面的总出现次数就会少1
stackTop--; // 出栈
}
// 5.4.2将当前字符入栈
stack[++stackTop] = currentChar;
}
// 6，给栈顶添加字符结束符
stack[++stackTop] = '\0';
return stack;
}六、杨辉三角
1，题目
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
2，题目分析
（1）第n行有n个元素，也就是说，杨辉三角的行数和列数是相等的
（2）使用a来表示一个二维数组，需要两层循环给二维数组的各个元素赋值
（3）现在用i和j来分别记录某个元素的行数和列数，那么a[i][j] = a[i-1][j-1] + a[i-1][j]
（4）需要处理一些边界情况，当j==0或者j==i的时候，元素值为0
（5）其实杨辉三角是可以使用递归去实现的，但是我们平常在写代码的过程中，尽量不要去使用递归，因为我在之前的文章中有过介绍，当使用递归的时候，会产生递归工作栈，进而浪费很多的内存空间。
3，代码分析
算法代码如下：
int ** yanghuiTriangle(int numberOfRows) {
// 为二维数组开辟空间
int **array = malloc(sizeof(int *) * numberOfRows);
// 开启两层循环为二维数组赋值
for (int row = 0; row < numberOfRows; row++) {
// 为对应的一维数组开辟空间
array[row] = malloc(sizeof(int) * (row + 1));
// 设置两个边界，头和尾都为1
array[row][0] = 1;
array[row][row] = 1;
// 头两行不需要走循环遍历，自第三行开始循环遍历
if (row <= 1) {
continue;
}
// 循环遍历给其他的元素赋值
for (int column = 1; column < row; column++) {
array[row][column] = array[row - 1][column - 1] + array[row - 1][column];
}
}
// 将二维数组返回
return array;
}在C语言中，一维数组可以使用int *来声明其类型，二维数组使用int **来声明其类型。二维数组中的元素是一维数组，一位数组中的元素是int类型。
如果是使用int **和int *来声明二维和一维数组，那么就需要使用malloc来为其开辟内存空间。
验证代码如下：
int main(int argc, const char * argv[]) {
int numberOfRows = 6;
int **array = yanghuiTriangle(numberOfRows);
for (int i = 0; i < numberOfRows; i++) {
printf("[");
for (int j = 0; j <= i ; j++) {
printf(" %d ", array[i][j]);
}
printf("]\n");
}
return 0;
}验证结果如下：
七、爬楼梯问题
1，题目
假设你正在爬楼梯，你需要爬n个台阶才能到达楼顶，每次你可以爬1个或者2个台阶，你有多少种方法可以爬到楼顶呢？注意：n是正整数。
2，递归的解法
首先需要说明一个观点，对于绝大部分的算法题目，递归其实并不是最优的解决方案，如果你可以想到其他的非递归方案，那么最好不要使用递归。
我们接下来使用递归的思想来分析一下该题目。
如果只有1个台阶，则有1种爬法，即：f(1)=1
如果有2个台阶，则有两种爬法（一次一步走2次，一次两步走1次），即：f(2)=2
如果有3个台阶，则根据第一次走一步还是两步分两种情况。
如果第一次走一步，那么还剩两步，剩下的这2步的走法是f(2)；
如果第一次走2步，那么还剩1步，剩下的这1步的走法是f(1);
因此，如果走3个台阶的话，总的走法个数是f(2)+f(1)。
如果有4个台阶，则根据第一次走1步还是2步分两种情况。
如果第一次走1步，那么还剩3步，剩下的这3步的走法是f(3)；
如果第一次走2步，那么还剩2步，剩下的这2步的走法是f(2);
因此，如果走4个台阶的话，总的走法个数是f(3)+f(2)。
......
以此类推，如果有n个台阶，则根据第一次走1步还是2步分两种情况。
如果第一次走1步，那么还剩n-1步，剩下的这n-1步的走法是f(n-1)；
如果第一次走2步，那么还剩n-2步，剩下的这n-2步的走法是f(n-2);
因此，如果走n个台阶的话，总的走法个数是f(n-1)+f(n-2)。我们知道，如果要使用递归，那么就必须要找到递归的出口，通过上面的分析可以知道，递归的出口就是n==1和n==2的时候。
代码如下：
int recursion(int numberOfSteps) {
if (numberOfSteps <= 0) {
return 0;
}
// 递归的出口
if (numberOfSteps == 1) {
return 1;
}
if (numberOfSteps == 2) {
return 2;
}
return recursion(numberOfSteps - 1) + recursion(numberOfSteps - 2);
}该算法的时间复杂度是O(2^n)。
3，动态规划法
所谓的动态规划法，是一种在数学、管理科学、计算机科学、经济学以及生物信息学中使用的，通过将原问题分解成相对简单的子问题的方式来求解复杂问题的方法。
动态规划法常常适用于有重叠子问题和最优子结构性质的问题，动态规划法的时间复杂度往往远低于朴素解法。
动态规划法背后的基本思想往往是非常简单的，大致上，如果要解一个给定问题，那么就需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划法往往用于优化递归问题，实际上我们这里的爬楼梯问题在采用上面的递归方式求解的时候，它就是一个斐波那契数列，它会重复计算很多的子问题，而如果使用动态规划法的话，就会节省很多的计算量。
采用动态规划法的时候，如果某个给定子问题的解已经求出，那么就将其记忆化存储，以便下一次需要同一个子问题解的时候直接查表。
接下来我们分析一下思路。
使用一个数组来记忆化存储，array[stepsNumber] = numberOfWays
如果只有1个台阶，则有1种爬法，即：array[1]=1
如果有2个台阶，则有两种爬法（一次一步走2次，一次两步走1次），即：array[2]=2
如果有3个台阶，则根据第一次走一步还是两步分两种情况。
如果第一次走一步，那么还剩两步，剩下的这2步的走法是array[2]；
如果第一次走2步，那么还剩1步，剩下的这1步的走法是array[1];
因此，如果走3个台阶的话，总的走法个数是array[2]+array[1]。
如果有4个台阶，则根据第一次走1步还是2步分两种情况。
如果第一次走1步，那么还剩3步，剩下的这3步的走法是array[3]；
如果第一次走2步，那么还剩2步，剩下的这2步的走法是array[2];
因此，如果走4个台阶的话，总的走法个数是array[3]+array[2]。
......
以此类推，如果有n个台阶，则根据第一次走1步还是2步分两种情况。
如果第一次走1步，那么还剩n-1步，剩下的这n-1步的走法是array[n-1]；
如果第一次走2步，那么还剩n-2步，剩下的这n-2步的走法是array[n-2];
因此，如果走n个台阶的话，总的走法个数是array[n-1]+array[n-2]。这样的话，我循环遍历stepsNumber次，自小到大依次获取到对应台阶数的走法，并依次记录到array中，等下一次遍历的时候直接去缓存的值即可，这样就不会重复进行计算。
代码如下：
int dynamicProgram(int numberOfSteps) {
if (numberOfSteps < 0) {
return 0;
}
// 初始化一个数组来记录对应台阶总数下的走法数量
int waysArray[numberOfSteps + 1];
waysArray[0] = 0;
waysArray[1] = 1;
waysArray[2] = 2;
// 遍历存储
for (int i = 3; i <= numberOfSteps; i++) {
waysArray[i] = waysArray[i - 1] + waysArray[i - 2];
}
return waysArray[numberOfSteps];
}该算法的时间复杂度是O(n)。可以看到，采用动态规划的方式比递归方式要节省不少的时间。
八、总结
我们在做算法题目的时候，不要一开始就考虑特殊场景，一开始先不要考虑得太复杂，一开始先将主体流程跑通，然后再慢慢去优化边界情况。
以上。
腾讯云开发者
