Note:- I am NOT asking you to write the program for me. I am NOT asking you to do the homework for me either. All I am asking you is if you could suggest an algorithm for me.
Present below are two algorithms. Can you please suggest me an algorithm to make the c++ program for them.Thanks in advance. :)
Problem 1 : Grid game
You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.
Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path.
Input format
The first line of the input contains one integer N, the number of rows and columns in the grid. Lines 2 to N+1 describe the N rows of the grid. Each of these N lines of input consists of N space separated integers, corresponding to the numbers in one row.
Notes
In all cases, N ≤ 2000. Each number in the grid is guaranteed to be less than 1000.
Sample Input
4
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8
--------------------------------------
Problem 2 : Choosing chocolates
Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.
Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.
Input format
The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.
Notes
In all cases, N ≤ 100,000.
Sample Input
10
30 10 8 20 11 12 25 13 20 19