Results 1 to 2 of 2
  1. #1
    stevenlin598 is offline Member
    Join Date
    Jun 2013
    Posts
    2
    Rep Power
    0

    Default how to develop dynamic programming solution

    I apologize if this question is too broad. I can often write a recursive backtracking solution, but don't know how to cache the answers into an appropriate array.
    For example:
    Java Code:
        public static int max(int[] costs, int index, int total, int shares) {
            if(index >= costs.length) {
               return total;
            }
            int buy = max(costs, index + 1, total - costs[index], shares + 1); // buy one stock
            int sell = max(costs, index + 1, total + shares * costs[index], 0); // sell all stocks
            return Math.max(total, Math.max(buy, sell)); // compares between buy, sell, and doing nothing
        }
    This is a dynamic programming exercise, but I have no idea what dimensions the dp array should be (I was thinking maybe dp[index][total][shares], but that seemed like overkill). Is this just because my understanding of recursion isn't solid enough or am I missing something else? This applies to every dp problem I try to solve, so general advice would be helpful.

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,985
    Rep Power
    9

    Default Re: how to develop dynamic programming solution

    We can't give you general advice, as the dimensions of the array depend entirely on the problem you're trying to solve. What does this method do? What does the array represent? You have to understand what the algorithm is doing before you can use it.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. Loop programming exercise. Need review of my solution.
    By Inky pinkie in forum New To Java
    Replies: 0
    Last Post: 09-21-2012, 05:55 PM
  2. android programming vs game programming using java
    By vgoel38 in forum Forum Lobby
    Replies: 2
    Last Post: 09-08-2012, 12:11 AM
  3. Java GUI Develop,emt
    By joaquin386 in forum New To Java
    Replies: 4
    Last Post: 04-24-2010, 02:04 PM
  4. develop mock ups
    By karthikeyan_raju in forum NetBeans
    Replies: 0
    Last Post: 10-19-2009, 03:58 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •