Dynamic Programming usage

[srinivasarao_kambala4]

Hi,

Which scenerios exactly used for the Dynamic programing in webdynproJava?

Thanks,

Srinivas

[Former Member]

Hi,

it depends on the concrete use case/problems you have, substructures you are using etc. In fact its plain math resp. physics, so I guess a reference to WD Java dont make sense. I would be also surprised if you will find any general Java API to implement this kind of segmentation algorithms: the concept of dynamic programming is in fact a basic approach to solve problems (NP stuff, if I remember right).

regards

[srinivasarao_kambala4]

Hi Lawarence,

Thanks for your quick responses.

if possible , can you pls explain with clearly with possible example.

Thanks

Srinivas

[Former Member]

Hi Srinivas,

your question is a bit to general as I mentioned, but I will try.

Lets assume you have a NP-hard problem, to keep it simple and well known: traveling salesman. Since P=NP is on the list of unsolved millenium problems (its a pitty Perelman is such a loneley guy, I would love to see him working on it, but thats another story), you need to work with heuristics and approximation.

So you, Srinivas, have found a sensational paradigma for dynamical optimizing of this problem, means in fact using subsets of results to solve this problem. If you implement your work on this manner, you are a dynamic programmer

As far I know, its not only used to solve NP stuff, but also for avoiding other problems. Lets take a look to a fibonacci implementation with constant memory usage and without stack overflow:

private java.math.BigInteger fibMemo2(Integer n)

    {

        if(memoliste.containsKey(n))

        {

            return memoliste.get(n);

        }

        else

        {

            java.math.BigInteger fib1 = fibMemo2(n - 1);

            memoliste.put(n-1, fib1);

            java.math.BigInteger fib2 = fibMemo2(n - 2);

            memoliste.put(n-2,fib2);

            memoliste.remove(n-3);

            return (fib1.add(fib2));

        }

    }

private java.math.BigInteger optimizedFib(int n)

{

    java.math.BigInteger erg = java.math.BigInteger.ZERO;

    for(int i = 1;i < n;i=i+200)

    {

        erg = fibMemo2(i);

    }

    erg = fibMemo2(n);

    return erg;

}

Srinivas, please remeber: I dont have any deep knowledge in working with such algorithms, so what Im saying is my understanding of the materia and dont have to be necessary right. What I know from my colleagues from the math faculty, the most cases of implementing of dynamic approaches orientating on well known algorithms and problems, like Dijkstra, Hirschberg, Viterbi and so on... To be able to help you better, just post your requirement.

regards