一道面试题引发------贪心算法解决多重循环问题

问题描述：



Analysis：
method1：暴力破解，从上到下，路径组合数随着和n呈指数增长，因此时间复杂度为O( )。
method2：方法1采用非递归方法，对应的也可以采用递归的方法进行计算，但是也需要求出所有的组合情况，因此时间复杂度仍然为O( ),优点是代码更加简洁。
递归和循环优缺点比较：
递归比循环的代码更加简洁，对有些复杂的问题使用递归实现比较简单；
递归因为在每次递归的时都要保存临时变量的值和运行状态，因此没有循环的运行效率高，递归的深度也收到程序运行时堆栈内存大小影响，有可能造成堆栈溢出，程序崩溃。
代码实现：

#include<iostream>
using namespace std;

int maxs = 0;//存储最大的值
int arr[100][100];// 存储n行数据
int n=0; 
void dp(int h,int index,int len)
{
    if(h == n)
    {
        if(len > maxs)
            maxs = len;
    }
    else
    {

        if(index >= 1)
        {
            dp(h+1,index-1,len+arr[h][index]);//左下 
        }
        dp(h+1,index,len+arr[h][index]);//下边 
        if(index <= n-2)
        {
            dp(h+1,index+1,len+arr[h][index]);//右下 
        }    
    }
}

int main()
{
    cin>>n;
    for(int i  = 0;i <n;i++)
    {

        int begin = (2*n-1)/2-i;
        int numbers = 2*(i+1)-1;
        for(int j = 0;j < numbers;j++)
        {
            int temp;
            cin>>temp;
            arr[i][begin++] = temp;
        }
    }
    dp(0,n/2,arr[0][(2*n-1)/2]);
    cout<<maxs<<endl;
}

运行结果：

method3：贪心算法，从第二行开始，每个数字与上面可能组成路径的情况有三个，将三个值中最大的和当前数相加来表示从第一层到该节点路径和最大的值，依次类推...,根据第n-1的结果求第n行从第一层到该节点路径和最大的值。最终遍历数列阵最后一行，找到第一层到最后一层路径和的最大值。
n层的数列矩阵含有的节点数为 ，除了第一个节点，求每个节点从第一层到该节点路径和最大值都需要和前一行三个节点进行比较，因此整个数列阵中总的操作为
因此贪心算法的时间复杂度为O( ) 循环方法的时间复杂度。
编程实现：

 #include<iostream>
using namespace std;

int maxs = 0;
int arr[100][100];
int n=0; 

void greedyGrid()
{
    //int tarr[100][100] = {0};
    for(int i = 1;i < n;i++)
    {
        int begin = (2*n-1)/2-i;
        int numbers = 2*(i+1)-1;
        for(int j = 0;j < numbers;j++)
        {
            int temp;
            int b = begin > 0?begin-1:begin;
            int e = begin < n-1?begin+1:begin;
            int maxvalue = arr[i-1][b];
            b++;
            while(b<=e)
            {
                if(arr[i-1][b] > maxvalue)
                    maxvalue = arr[i-1][b];
                b++;
            }
            arr[i][begin] = maxvalue +arr[i][begin];
            begin++;    
        }
    }
    maxs = arr[n-1][0];
    for(int i = 1;i < 2*n-1;i++)
    //for(int i = 1;i <　2*n-1;i++)
    {
        if(arr[n-1][i] > maxs)
        {
            maxs = arr[n-1][i];
        }
    }
}
int main()
{
    cin>>n;
    for(int i  = 0;i <n;i++)
    {

        int begin = (2*n-1)/2-i;
        int numbers = 2*(i+1)-1;
        for(int j = 0;j < numbers;j++)
        {
            int temp;
            cin>>temp;
            arr[i][begin++] = temp;
        }
    }
    greedyGrid();
    cout<<maxs<<endl;
}

运行结果：