0

Dear Computer Science experts,

I have a question regarding Dynamic Programming (DP). The problem is I am given a sentence of characters and a cost_list that contains a list of substrings of sentence with their costs, the goal is to find lowest cost. It is assumed that cost_list contains all the substrings in sentence.

For example, suppose I have the below parameters,

sentence = "xxxyyzz"

cost_list = [["x", 1], ["xx", 3], ["y", 3], ["yy", 1], ["z", 2]]

So sentence could be [xx][x][yy][z][z], so the total cost is 3 + 1 + 1 + 2 + 2 = 9

But I could also select the substrings in sentence in a different way and we have [x][x][x][yy][z][z], which gives us 1 + 1 + 1 + 1 + 2 + 2 = 8 and it is the lowest cost.

The question is to construct a Dynamic Programming algorithm find_lowest_cost(sentence, cost_list).

Below is my recursive function for this problem I created, I have tested and it is correct,

def find_lowest_cost(sentence, cost_list):
   if len(sentence) == 0:
       return 0
   else:
       result = []
       possible_substrings = []
       possible_costs = []
       for c in cost_list:
           current_substring = c[0]
           current_cost = c[1]

           if current_substring == sentence[0:len(current_substring)]:
               possible_substrings.append(current_substring)
               possible_costs.append(current_cost)

       for i in range(0, len(possible_substrings)):
           result.append(possible_costs[i] + find_lowest_cost(sentence[len(possible_substrings[i]):], cost_list))

       return min(result)


sentence = "xxxyyzz"
cost_list = [["x", 1], ["xx", 3], ["y", 3], ["yy", 1], ["z", 2]]
print(find_lowest_cost(sentence, cost_list))

I am stuck on how to converting the Recursion to Dynamic Programming (DP).

Question 1: For DP table, my columns are the characters of sentence. How what should my rows be? My thinking is it can't be a rows of "x", "xx", "y", "yy" and "z" because how would we compare "yy" with, say only "y" in sentence?

Question 2: Suppose rows and columns are figured out, at the current cell, what should the current cell be built upon? My notion is the cell is built-upon the lowest value of previous cells, such as cell[row][col-1], cell[row-1][col] and cell[row-1][col-1]?

Thanks!

Improve this question
6
  • Welcome to Stack Overflow. Please be aware this is not a code-writing or tutoring service. We can help solve specific, technical problems, not open-ended requests for code or advice. Please edit your question to address a single question, show what you have tried so far, and what specific problem you need help with. See the How To Ask a Good Question page for details on how to best help us help you. Commented Oct 30, 2021 at 18:39
  • Hi, I just need help on my two questions that I have difficulty with. I did mention my thinking and need if my logic is correct. Commented Oct 30, 2021 at 18:49
  • 1
    This site is best used once you have a specific problem that you can't figure out, general questions asking for guidance doesn't fit with SO's objectives. Commented Oct 30, 2021 at 18:51
  • My biggest problem is all other DP questions are 1-1 comparison, 1 character compared with another character, but the problem I'm facing is multiple in-order characters comparison, why I am not familiar with. I will modify my question in an hour as I am still in process of getting the DP table from Recursion. Commented Oct 30, 2021 at 18:58
  • Sorry, I don't know how to solve the DP table. My guess is this one also requires me to do the 3D DP table thing, which I am not familiar with. This is what I dislike about Computer Science at my school, which is top 20 best university in the world, Profs teach easy questions that can be found online but the homework problems are multiply difficult. Commented Oct 30, 2021 at 22:24

1 Answer 1

Reset to default
0

Once you are able to get the recursive solution then try to look for how many variable are getting changed. Analysing the recursive approach:

We need to find a solution like, what is the minimum cost when string is having length 1, then 2 so on... There would be repetitive calculation for substring from 0 to k th index so we need to store all calculated result into single dp so that we can give the answer of any k th index which has already calculated. Below is my Java solution.

import java.util.HashMap;
public class MyClass {
    private static Integer[] dp;
    public static void main(String args[]) {
        // cost_list = [["x", 1], ["xx", 3], ["y", 3], ["yy", 1], ["z", 2]]
        HashMap<String, Integer> costmp = new HashMap();
        costmp.put("x", 1);
        costmp.put("xx", 3);
        costmp.put("y", 3);
        costmp.put("yy", 1);
        costmp.put("z", 2);
        
        String sentence = "xxxyyzz";
        // String sentence = "xxyyzzxxxxyyyyxxxyxxyyyxxyyyzzzyyyxxxyyyyzzzyyyyxxxyyyzzzyyxxxxxxxxxxxxxxyyxyxyzzzzxxyyxx";
        // String sentence = "xxxyyzzxxxxyyyyxxxyxxyyyxxyyyzzzyyyxxxyyyyzzzy";
        dp = new Integer[sentence.length()+1];
        int res = find_lowest_cost(sentence, costmp, 0);
      System.out.println("find_lowest_cost = " + res);
    }


    private static int find_lowest_cost(String sentence, HashMap<String, Integer> costmp, int st)
    {
        if(st == sentence.length())
            return 0;
        int mincost = Integer.MAX_VALUE;
        if(dp[st] != null)
            return dp[st];
        String str = new String();
        for(int i = st;i < sentence.length(); i++)
        {
            str+=sentence.charAt(i);
            if(!costmp.containsKey(str))
                break;
            int cost = costmp.get(str);
            mincost = Math.min(mincost, cost+find_lowest_cost(sentence, costmp, i+1));
        }
        dp[st] = mincost;
        return mincost;
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.