Dynamic programming

  • 1

    Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n. In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string ,s , of movement instruction consisting of the letters 1 and r , where 1 is an instruction to move one step left and r is an instruction to move one step right.
    Jamie followed the instructions in s one by one and in order .For Example if s=‘rrlr’,she performs the following sequence of moves :one step right ->one step right ->one step left -> one step right .Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. recall that a subsequence of a string is obtained by deleting zero or more characters from string .

    it has four parameters
    A String , s giving a sequence of eduction using the characters l( i.e. move left one unit ) and r (i.e. move right one unit)
    An integer n, denoting the length of the number line.
    An integer x, denoting jamie’s starting point on the number line
    An integer y , denoting Jamie’s enidng point on the number line.
    The function must return an integer denoting the total number of distinct subsequence of string s that will lead Jamie from point x to point y as this value cab be quite large .

    Sample Input

    out put =7

  • 1

    If I understand the phrasing of the problem correctly, I believe the output to the sample input is 9.
    using a function substring(string, begin, length):
    substring('rrlrlr', 0, 1) = 'r'
    substring('rrlrlr', 1, 1) = 'r'
    substring('rrlrlr', 0, 3) = 'rrl'
    substring('rrlrlr', 3, 1) = 'r'
    substring('rrlrlr', 1, 3) = 'rlr'
    substring('rrlrlr', 0, 5) = 'rrlrl'
    substring('rrlrlr', 5, 1) = 'r'
    substring('rrlrlr', 3, 3) = 'rlr'
    substring('rrlrlr', 1, 4) = 'rlrlr'

    If this is the correct interpretation of "distinct subsequences", then I can propose a solution.

  • 0

    Solution please someone

  • 0

    This is without memoization. But we can add memoization.

    Set<String> set = new HashSet<String>();
        private int findWays(String input, int length, int x, int y) {
             findWaysHelper(input,length,x,y,0,new StringBuilder(),set);
             return set.size();
        private void findWaysHelper(String input, int length, int x, int y,int currentIndex,StringBuilder path,Set<String> set) {
            if(currentIndex<0 || currentIndex>=length)
            char c = input.charAt(currentIndex);
            findWaysHelper(input,length,x,y,currentIndex+1,path,set); //dont include
                findWaysHelper(input,length,x+1,y,currentIndex+1,path.append("r"),set); //include this
                findWaysHelper(input,length,x-1,y,currentIndex+1,path.append("l"),set); //include this

  • 0
    This post is deleted!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.