Rod Cutting- GFG

This one was a medium level prob and took some time to grasp the idea. 

Provided the Time Complexity that was expected it made things a lil clear, overall it's a DP Problem, that just maintains the profits in a single D Array, and tries to get the overall optimal solution from the optimal solutions of the subproblems, feels like I am writing some ADA answer, 

well, that's what was required in the prob, it is a perfect and simple(maybe)  example for understanding this Concept of Overlapping Subproblems in Dynamic Programming.

DP has 2 main properties that is, Overlapping Subproblems and Optimal Substructue, these basically are used to check if the problem is of DP or not.

Cause if one of this is satisfied then only the use of DP will be of any use, cause if there none of these then it can be possible that either Greedy or Divide and Conquer may, work or maybe it's just a normal prob on some logic completely diff.

Also, it was a coincident that I got this prob today cause tomorrow I have ADA test, it's preparation was quite smooth but I obviously had to invest some hours but it wasn't much work because it's conceptual and most of the theory is relevant to the concepts I have understood or somewhat dependent on one other.

Stick to the Topic🤣

Most of the topics in the Sub are quite common, like DP and it's algos, the Backtracking, Greedy, just had to do the revision for Branch and Bound then B tree, all the Graph algos revision and then a numerical on Huffman Coding cause that's asked quite a lot. 

Also those p,np,np-hard and np-complete, that was a bit off the topic thing for me cause it's like something that would never come to any use or maybe cause it doesn't make any sense to me, so it took much time than expected.

But, overall the Sub is fine, day after tomorrow will be SE which I have started to develop more interest on, thinking about the importance of it in the development of a Project cause I saw that most of the Project that I have developed have somewhat linked to the points that are mentioned in the Subject.

Well, I submitted the solutions and maybe I'll also take the next prob right now cause I may not be able to think about one tomorrow, so will try to solve it and then hit the hay.

Code Implementation for the Problem:-

class Solution{

  public:

    int cutRod(int arr[], int n){

        int dp[n];

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

            dp[i] = arr[i];

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

                dp[i] = max(dp[i], dp[i-j-1]+arr[j]);

        }

        return dp[n-1];

    }

};