题目的主要信息：

题目给出了一个杨辉三角的变形三角形，这个变形三角形中的每一个数字是他肩上三个数之和。
我们需要根据输入的行号，求出相应行第一个偶数出现的位置。

方法一：

这个三角是有规律的，我们可以多列几行来找其中的规律，如下图所示： alt 可以发现以下规律：

小于等于两行是没有偶数的
行号能被4整除，偶数在第三位
行号除4余2的话，偶数在第四位
其余情况，偶数在第三位因此，我们可以写一个程序直接判断当前行号第一个偶数的位置

具体做法：

#include<iostream>
using namespace std;
int main(){
    int num;
    while(cin>>num){
        if(num<=2) cout<<-1<<endl;//小于等于两行的话是没有偶数的
        else if(num%4 == 0) cout<<3<<endl;//能被4整除，偶数在第三位
        else if(num%4 == 2) cout<<4<<endl;//余2的话，偶数在第四位
        else cout<<2<<endl;//其余情况在第二位
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，判断语句只需要常数时间。
空间复杂度： $O (1)$ ，只使用了常数空间。

方法二：

我们可以用一个二维vector来模拟杨辉三角的变形三角形。

第n行的长度为 $2 * n - 1$ 。
如果总共有n行，第一行的元素位置为n-1，且最后一行的第一个数字和最后一个数字都为1，其余部分用0初始化。

知道这两条以后我们就可以对整个数组初始化，得到2*（2n-1）大小的数组。然后从第二行开始，逐个计算每个元素的值。最后得到n行的三角形，遍历一遍最后一行的所有元素，输出遇到的第一个偶数的列号，否则输出-1。但是这个方法占用的空间较大，会超过本题的内存限制，无法通过最后一个样例。 alt

具体做法：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        vector<vector<int>> triangle(n,vector<int>(2*n-1,0));
        triangle[0][n-1]=1;//第一行初始化为1
        triangle[n-1][0]=1;//第n行的第一位初始化为1
        triangle[n-1][2*n-2]=1;//第n行的最后一位初始化为1
        for(int i=1;i<n;i++){//计算数组中每个位置的值
            for(int j=1;j<2*n-2;j++){
                triangle[i][j]=triangle[i-1][j-1]+triangle[i-1][j]+triangle[i-1][j+1];//肩上三个数相加
            }
        }
        int flag=0;
        for(int i=0;i<2*n-1;i++){//遍历第n行
            if(triangle[n-1][i]!=0){
                if(triangle[n-1][i]%2==0){//找到碰到的第一个偶数
                    cout<<i+1<<endl;//输出列号
                    flag=1;
                    break;
                }
            }
        }
        if(flag==0) cout<<-1<<endl;//没有找到偶数则输出-1
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，计算每个位置的值的时候有两重循环。
空间复杂度： $O (n^{2})$ ，用一个二维vector储存三角形。

题解 | #杨辉三角的变形#

题目的主要信息：

方法一：

方法二：