Example Input/Output:

Input:

9

Output:

34

Example Input/Output:

Input:

2

Output:

1

C-code

Compiler

#include<stdio.h>

void fib(int N)

{

int fi[N];

fi[0]=0;

fi[1]=1;

for(int i=2;i<=N;i++)

fi[i]=fi[i-1]+fi[i-2];

printf("%d",fi[N]);

}

void main()

{

int N;

scanf("%d",&N);

fib(N);

}

A kids game has a board with an M*N matrix having M rows and N columns containing non-negative integer values as cell values.The kid can start from the first column of any row and can perform the following three navigations collecting the points in that cell.

-He can move to the right cell.

-He can move to the top right cell.

-He can move to the bottom right cell.

The kid cannot come back to a previous column.He navigates until he reaches the last column of the matrix a collects the points in each cell.The program must print the maximum points a kid can collect for the given matrix while navigating.

Example1:

Input:

3 3

5 3 3

2 1 4

0 9 4

Output:

15

Explanation:

• maximum points can be collected by 2->9->4.Hence 15(2+9+4).

Example2:

Input:

4 4

1 3 1 5

2 2 4 1

5 0 2 3

0 6 1 2

Output:

16

Explanation:

• maximum points can be collected by 5->6->2->3 or 5->2->4->5.Hence 16(5+6+2+3) or 16(5+2+4+5).

C-Code

Compiler

#include<stdio.h>

int max(int n1,int n2)

{

if(n1>n2)

return n1;

else

return n2;

}

int max1(int n1,int n2,int n3)

{

if(n1>=n2&&n1>=n3)

return n1;

else if(n2>=n1&&n2>=n3)

return n2;

else if(n3>=n1&&n3>=n2)

return n3;

}

int main() {

int r,c,maxprize=0;

scanf("%d %d\n",&r,&c);

int arr[r][c],prize[r][c];

for(int i=0;i<r;i++)

{

for(int j=0;j<c;j++)

{

scanf("%d ",&arr[i][j]);

if(j==0)

prize[i][0]=arr[i][j];

}

}

for(int col=1;col<c;col++)

{

for(int row=0;row<r;row++)

{

if(row==0)

{

prize[row][col]=max(prize[row][col-1],prize[row+1][col-1])+arr[row][col];

}

else if(row==r-1)

{

prize[row][col]=max(prize[row][col-1],prize[row-1][col-1])+arr[row][col];

}

else

{

prize[row][col]=max1(prize[row][col-1],prize[row-1][col-1],prize[row+1][col-1])+arr[row][col];

}

if(col==c-1)

{

if(prize[row][col]>maxprize)

maxprize=prize[row][col];

}

}

}

printf("%d",maxprize);

}