You have ‘n’ mixtures, arranged in a row. Each mixture…

0

You have n mixtures, arranged in a row. Each mixture has one of 100 different colors (colors have numbers from 0 to 99). You wants to mix all these mixtures together. Ateach step, you are going to take two mixtures that stand next to each other and mix them together, and put the resulting mixture in their place. When mixing two mixtures of colors a and b, the resulting mixture will have the color (a+b) mod 100. Also, there will be some smoke in the process. The amount of smoke generated when mixing two mixtures of colors a and b is a*b. What is the complexity of algorithm that returns the minimum amount of smoke that you can get when mixing all the mixtures together.

plz help me wth the approach..

Ravi Garg edited question
    0
    Tanusree Ray (anonymous)

    yes fibo will not work as its askng minimum smoke is reqrd.. it can be done like matrix chain multplctn of DP.. nd the complexty is O(n^2.81) whch can be taken as O(n^3)..

    Tanusree Ray answered
      0
      Niraj Kant Sinha (anonymous)

      could you paste your code alteast the recursion part.

      Niraj Kant Sinha answered
        0
        Shikhill Gupta (anonymous)

        can we take mixture from anywhere Joel Shrey:plz make it clear

        Shikhill Gupta answered
          0
          Niraj Kant Sinha (anonymous)

          The color of dp[i,j] is independent order of the mixtures that is to figured out.

          Niraj Kant Sinha answered
            0
            Tanusree Ray (anonymous)

            can dis problem be approachd using the fibonacci series concept??

            Tanusree Ray answered
              Add image to editor add image from link

              Question stats

              • Active
              • Views1026 times
              • Answers10 answers
              • Followers1 follower
              Question and answer is powered by AnsPress