You are given a single positive integer n, 2 For n=7, the best two options are:...

  

Transcribed Image Text:

You are given a single positive integer n, 2 For n=7, the best two options are: Sum 7=3+4 7=3+2+2 The computational complexity of your program should be O(n). Use dynamic programming to achieve that complexity. Examples: INPUT 2 3 STI 4 10 5 01 6 7 Product 12=3*4 12=3*2*2 Hint: OUTPUT 1 2 4 6 9 12 Consider the similarities between this problem for input "n" and the rod cutting problem with input rod of length "n", and then adapt the dynamic programming solution from rod cutting to this problem. You are given a single positive integer n, 2 For n=7, the best two options are: Sum 7=3+4 7=3+2+2 The computational complexity of your program should be O(n). Use dynamic programming to achieve that complexity. Examples: INPUT 2 3 STI 4 10 5 01 6 7 Product 12=3*4 12=3*2*2 Hint: OUTPUT 1 2 4 6 9 12 Consider the similarities between this problem for input "n" and the rod cutting problem with input rod of length "n", and then adapt the dynamic programming solution from rod cutting to this problem.

Answer rating: 100% (QA)

Program Code ... View the full answer