Write a function named rodCutting that solves the classic "rod cutting" problem using dynamic programming.
The idea is that you are given a rod that can be cut into pieces of various sizes and sold, where each piece fetches a given price in return, and you are trying to find the optimal way to cut the rod to generate the greatest total price.
For example, suppose you have a rod as shown in the following figure that can be cut into pieces of length 1-8:
length 1 2 3 4 5 6 7 8
rod =================================
price 1 5 8 9 10 17 17 20
Your function accepts a reference to a vector of integers representing the various sizes that can be cut, from 1 through the length of the rod inclusive.
For the rod in the preceding figure, the vector would contain the values {1, 5, 8, 9, 10, 17, 17, 20}.
You should return an integer representing the maximum sum that can be obtained by cutting the rod into pieces of any length.
For the rod in the preceding figure, the correct answer is to return 22, which is obtained by cutting the rod into pieces of lengths 2 and 6.
The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach.
Do not use recursion.
You are allowed to construct any data structures (array, vector, set, map, etc.) necessary to store the data for your dynamic programming algorithm.
You may assume that the values are in nondecreasing order in the vector and that none of the values in the vector are negative.
