Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts

Shortest Way To Collect Items In Retail Store

Wednesday, 14 October 2015 | Posted by
This problem related to retail industry. Retail company XYZ have some number of stores. It is providing website for its users, By using this site, users can select items and pickup them from store itself. Here the website makers has to provide shortest path to collect items from the store.

Observe the below Store Map

  1. Blue Node is Starting node (Point where user starts)
  2. Green Node is End node (Point of billing)
  3. Black Nodes are intermediate nodes
  4. Red Nodes are points of item

Basic Algorithm

  1. The basic algorithm is so simple.
  2. Start from starting point, connect next shortest Red node
  3. Connect next unvisited shortest red node from current red node
  4. Connect Green node from current red node

Depth of this algorithm

Now we will go in depth of this algorithm. How will we find shortest red node ?. Here we have to use intermediate nodes (black nodes) with dijkstras algorithm to find shortest distance (Creating Minumum Spanning Tree).  
  1. Find nearest node by dijkstras algorithm from starting node. Now customer will go from starting node to that nearest node and will pick his item.
  2. Then find nearest node from the node where customer picked the item. This node must be other than customer visited item node. Now customer will go from starting node to that nearest node and will pick his item.
  3. Complete 2nd step until customer collects all items.
  4. Then find nearest route from the current item node to target node. Now customer will go through that route and will reach to target billing node

Java Code

Node.java
import java.util.ArrayList;

public class Node implements Comparable<Node>{
    double x;
    double y;
    boolean isVisited;
    boolean isTarget;
    boolean isSource;
    boolean isMainNode;
    ArrayList<Edge> edges = new ArrayList<Edge>();
    double tDist = -1;
    int val;
    ArrayList<Edge> connectingEdges = new ArrayList<Edge>();
    
    public Node(int i, double x, double y, boolean isVisited, boolean isTarget, boolean isSource, boolean isMainNode) {
        this.val = i;
        this.x = x;
        this.y = y;
        this.isVisited = isVisited;
        this.isTarget = isTarget;
        this.isSource = isSource;
        this.isMainNode = isMainNode;
    }
    
    public double getX() {
        return x;
    }
    public void setX(double x) {
        this.x = x;
    }
    public double getY() {
        return y;
    }
    public void setY(double y) {
        this.y = y;
    }
    public boolean isVisited() {
        return isVisited;
    }
    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }
    public boolean isTarget() {
        return isTarget;
    }
    public void setTarget(boolean isTarget) {
        this.isTarget = isTarget;
    }
    public boolean isSource() {
        return isSource;
    }
    public void setSource(boolean isSource) {
        this.isSource = isSource;
    }
    public void addEdge(Edge ed) {
        edges.add(ed);
    }
    public void addConnectingEdge(Edge ed) {
        connectingEdges.add(ed);
    }
    
    
    @Override
    public String toString() {
        return "Node "+val;
    }

    @Override
    public int compareTo(Node o) {
        if(o.val ==  this.val) {
            return 0;
        } else {
            return 1;
        }
    }

    public void addConnectingEdge(ArrayList<Edge> connectignEdges2) {
        connectingEdges.addAll(connectignEdges2);
    }
}
Edge.java
public class Edge {
    Node nd1;
    Node nd2;
    double distance;

    public Edge(Node nd1, Node nd2) {
        this.nd1 = nd1;
        this.nd2 = nd2;
        double xsq = (nd1.x - nd2.x) * (nd1.x - nd2.x);
        double ysq = (nd1.y - nd2.y) * (nd1.y - nd2.y);
        distance = Math.sqrt(xsq + ysq);
        nd1.addEdge(this);
        nd2.addEdge(this);
    }

    public Node getNd1() {
        return nd1;
    }

    public void setNd1(Node nd1) {
        this.nd1 = nd1;
    }

    public Node getNd2() {
        return nd2;
    }

    public void setNd2(Node nd2) {
        this.nd2 = nd2;
    }

    public double getDistance() {
        return distance;
    }

    public void setDistance(double distance) {
        this.distance = distance;
    }

    @Override
    public String toString() {
        return "Edge["+nd1.val+", "+nd2.val+"]";
    }

}

GreedyPath.java 
import java.util.ArrayList;

public class GreedyPath {
   
   public static void main(String[] args) {
      Node nd1 = new Node(1, 15, 15, false, false, false, false);
      Node nd2 = new Node(2, 35, 15, false, false, true, false);
      Node nd3 = new Node(3, 55, 15, false, false, false, false);
      
      Node nd4 = new Node(4, 15, 75, false, false, false, false);
      Node trg = new Node(5, 35, 75, false, true, false, false);
      Node nd6 = new Node(6, 55, 75, false, false, false, false);
      
      Node mn1 = new Node(7, 15, 60, false, false, false, true);
      Node mn2 = new Node(8, 35, 45, false, true, false, true);
      Node mn3 = new Node(9, 55, 25, false, false, false, true);
      
      ArrayList<Node> aln = new ArrayList<Node>();
      aln.add(nd1);
      aln.add(nd2);
      aln.add(nd3);
      aln.add(nd4);
      aln.add(trg);
      aln.add(nd6);
      aln.add(mn1);
      aln.add(mn2);
      aln.add(mn3);
      
      new Edge(nd1,nd2);
      new Edge(nd2, nd3);
      new Edge(nd4, trg);
      new Edge(trg, nd6);
      
      new Edge(nd1,mn1);
      new Edge(nd4, mn1);
      new Edge(nd2, mn2);
      new Edge(trg, mn2);
      new Edge(nd3, mn3);
      new Edge(nd6, mn3);
      
      ArrayList<Node> mainPathNodes = new  ArrayList<Node>();
      ArrayList<Edge> mainPathEdges = new  ArrayList<Edge>();
      Node src = nd2;
      mainPathNodes.add(src);
      while(true) {
          resetNodes(aln);
          ArrayList<Node> connected = new  ArrayList<Node>();
          createMinimumSpanningTree(src, aln, connected, 0);
          
          Node minMainNode = null;
          double minDist = Double.MAX_VALUE;
          for(Node nd:connected) {
              if((nd.isMainNode && minDist > nd.tDist) && !mainPathNodes.contains(nd) && nd.val != src.val) {
                  minMainNode = nd;
                  minDist = nd.tDist;
              }
          }
          
          if(minMainNode!=null) {
              mainPathNodes.add(minMainNode);
              mainPathEdges.addAll(minMainNode.connectingEdges);  
              src = minMainNode;
          } else {
              mainPathNodes.add(trg);
              mainPathEdges.addAll(trg.connectingEdges);
              break;
          }
          
      }
      
      System.out.println(mainPathNodes);
      System.out.println(mainPathEdges);
   }
   
   public static void createMinimumSpanningTree(Node src, ArrayList<Node> nodes, ArrayList<Node> connected, double dist) {
       src.tDist = dist;
       src.setVisited(true);
       connected.add(src);
       
       Node minNode = null;
       Node supMinNode = null;
       double minDist = Double.MAX_VALUE;
       Edge minEdge = null;
       for(Node nd:connected) {
           for(Edge ed:nd.edges) {
               if(nd.val == ed.nd1.val) {
                   if(!ed.nd2.isVisited) {
                       double tDist = nd.tDist + ed.distance;
                       if(tDist < minDist) {
                           minDist = tDist;
                           minNode = ed.nd2;
                           minEdge = ed;
                           supMinNode = ed.nd1;
                       }
                   }
               } else {
                   if(!ed.nd1.isVisited) {
                       double tDist = nd.tDist + ed.distance;
                       if(tDist < minDist) {
                           minDist = tDist;
                           minNode = ed.nd1;
                           minEdge = ed;
                           supMinNode = ed.nd2;
                       }
                   }
               }
           }
       }
       
       if(minNode != null) {
           minNode.addConnectingEdge(supMinNode.connectingEdges);
           minNode.addConnectingEdge(minEdge);
           createMinimumSpanningTree(minNode, nodes, connected, minDist);
       }
   }
   
   public static void resetNodes(ArrayList<Node> aln) {
       for(Node nd:aln) {
           nd.setVisited(false);
           nd.tDist = Double.MAX_VALUE;
           nd.connectingEdges.clear();
       }
   }
   
}

Read More
Labels:,, | 37 comments

Break Word Into Dictionary Words Using JavaScript

Thursday, 2 July 2015 | Posted by

Problem

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example

Given s = "SodhanaLibrary", dict = ["Sodhana", "Library"].
Return true because "SodhanaLibrary" can be segmented as "Sodhana Library".

JavaScript Code

function wordBreak(s, dict) {
    var t = [];
    for(var i=0; i<=s.length; i++){
        t[i] = false;
    }
    t[0] = true; //set first to be true, why?
    //Because we need initial state

    console.log(t);
    for(var i=0; i<s.length; i++){
        //should continue from match position
        if(!t[i]) 
            continue;

        for(var a in dict){
            var len = dict[a].length;
            var end = i + len;
            if(end > s.length)
                continue;

            if(t[end]) continue;

            if(s.substring(i, end) == dict[a]){
                t[end] = true;
            }
        }
        console.log(t);
    }

    return t[s.length];
}
var s = "sodhanalibrary";
var dict = ["sodhana", "library"];
console.log(wordBreak(s,dict));
Read More
Labels:,, | 4 comments

Combinations Sum Using JavaScript

Saturday, 27 June 2015 | Posted by

Problem

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.

Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, ... , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7,
A solution set is:

[7] 
[2, 2, 3] 

JavaScript Code

function combinationSum(candidates, target) {
    var result = [];
 
    if(candidates == null || candidates.length == 0) return result;
 
    var current = [];
    candidates.sort();
 
    combinationSumHelper(candidates, target, 0, current, result);
 
    return result;
}
 
function combinationSumHelper(candidates, target, j, curr, result){
   if(target == 0){
       var temp = curr.slice();
       result.push(temp);
       return;
   }
 
   for(var i=j; i<candidates.length; i++){
       if(target < candidates[i]) 
            return;
       curr.push(candidates[i]);
       combinationSumHelper(candidates, target - candidates[i], i, curr, result);
       curr.pop(); 
   }
}

With Unique Combinations

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used ONCE in the combination.

Note:
1) All numbers (including target) will be positive integers.
2) Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
3) The solution set must not contain duplicate combinations.

JavaScript Code

var result = [];

function combinationSum(num, target) {
    result = [];
    if(num == null || num.length == 0)
        return result;
 
    num.sort();            
 
    var temp = [];    
    getCombination(num, 0, target, temp, result);
}
function getCombination(num, start, target, temp){
    if(target == 0){
        var t = JSON.parse(JSON.stringify(temp));
        if(indexOf(result, t, arraysIdentical)  == -1) {
            result.push(t);
        }
        return;
    }
 
    for(var i=start; i<num.length; i++){
        if(target < num[i])
            continue;
 
        temp.push(num[i]);
        getCombination(num, i+1, target-num[i], temp, result);
        temp.pop();
    }
}

function arraysIdentical(arr1, arr2) {
    var i = arr1.length;
    if (i !== arr2.length) {
        return false;
    }
    while (i--) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }
    return true;
}

function indexOf(arr, val, comparer) {
    for (var i = 0, len = arr.length; i < len; ++i) {
        if ( i in arr && comparer(arr[i], val) ) {
            return i;
        }
    }
    return -1;
}
Read More
Labels:,, | 4 comments

Combinations (N C K) Using JavaScript

| Posted by

Problem

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example  

If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

JavaScript Code

function combine(n, k) {
    var result = [];
 
    //illegal case
    if (k > n) {
        return null;
    //if k==n
    } else if (k == n) {
        var temp = [];
        for (var i = 1; i <= n; i++) {
            temp.push(i);
        }
        result.push(temp);
        return result;
    //if k==1
    } else if (k == 1) {
 
        for (var i = 1; i <= n; i++) {
            var temp = [];
            temp.push(i);
            result.push(temp);
        }
 
        return result;
    }
 
    //for normal cases, initialize a list with one element
    for (var i = 1; i <= n - k + 1; i++) {
        var temp = [];
        temp.push(i);
        result.push(temp);
    }

    
    return combineHelper(n, k, result);
}
 
function combineHelper(n, k, result) {
    
    var prevResult = result.slice();
 
    if(result[0].length == k) return result;
 
    result = [];
    for (var j=0; j<prevResult.length; j++) {
            var one = prevResult[j];
        for (var i = 1; i <= n; i++) {
            if (i > one[one.length - 1]) {
                var temp = one.slice();
                temp.push(i);
                result.push(temp);
            }
        }
    }
 
    return combineHelper(n, k, result);
}

Using Depth First Search

var result = [];

function combine(n, k) {
    if (n <= 0 || n < k)
        return result;
 
    var item = [];
    dfs(n, k, 1, item); // because it need to begin from 1
}
 
function dfs(n, k, start, item) {
    if (item.length == k) {
        result.push(item.slice());
        return;
    }
 
    for (var i = start; i <= n; i++) {
        item.push(i);
        dfs(n, k, i + 1, item);
        item.pop();
    }
}
Read More
Labels:,, | 1 comments

Generate Panenthesis Using JavaScript

| Posted by

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example

Given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

JavaScript Code

function generateParenthesis(n) {
    var result = [];
    var diff = [];
 
    result.push("");
    diff.push(0);
 
    for (var i = 0; i < 2 * n; i++) {
        var temp1 = [];
        var temp2 = [];
 
        for (var j = 0; j < result.length; j++) {
            var s = result[j];
            var k = diff[j];
 
            if(i < 2 * n - 1) {
                temp1.push(s + "(");
                temp2.push(k + 1);
            }
 
            if (k > 0 && i < 2 * n - 1 || k == 1 && i == 2 * n - 1) {
                temp1.push(s + ")");
                temp2.push(k - 1);
            }
        }
 
        result = JSON.parse(JSON.stringify(temp1));
        diff = JSON.parse(JSON.stringify(temp2));
    }
 
    return result;
}
Read More
Labels:,, | 0 comments

Find Kth Permutation Using JavaScript

| Posted by

Problem

The set [1,2,3,…,n] contains a total of n! unique permutations.

Example

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence. (Note: Given n will be between 1 and 9 inclusive.)

JavaScript Code

function getPermutation(n, k) {
     
    // initialize all numbers
    var numberList = [];
    for (var i = 1; i <= n; i++) {
        numberList.push(i);
    }
    // change k to be index
    k--;

    // set factorial of n
    var mod = 1;
    for (var i = 1; i <= n; i++) {
        mod = mod * i;
    }
    var result = "";

    // find sequence
    for(var i = 0; i < n; i++) {
        mod = mod / (n - i);
        // find the right number(curIndex) of
        var curIndex = k / mod;
        // update k
        k = k % mod;

        // get number according to curIndex
        result += numberList[curIndex];
        // remove from list
        numberList.splice(curIndex,1);
    }

    return result;
}
Read More
Labels:,, | 0 comments

Generate Unique Permutations From The Collection Of Duplicate Items Using JavaScript

| Posted by

Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example

[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

JavaScript Code

function permute(num) {
    var result = [];
 
    //start from an empty list
    result.push([]);
 
    for (var i = 0; i < num.length; i++) {
        //list of list in current iteration of the array num
        var current = [];
 
        for (var k=0;k<result.length;k++) {
            var l = result[k];
            // # of locations to insert is largest index + 1
            for (var j = 0; j < l.length+1; j++) {
                // + add num[i] to different locations
                l.splice(j, 0, num[i]);
 
                var temp = JSON.parse(JSON.stringify(l));
                if(indexOf(current, temp, arraysIdentical)  == -1) {
                       current.push(temp);
                }
                    
                
                // - remove num[i] add
                l.splice(j,1);
            }
        }
 
        result = JSON.parse(JSON.stringify(current));
    }
 
    return result;
}

function arraysIdentical(arr1, arr2) {
    var i = arr1.length;
    if (i !== arr2.length) {
        return false;
    }
    while (i--) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }
    return true;
}

function indexOf(arr, val, comparer) {
    for (var i = 0, len = arr.length; i < len; ++i) {
        if ( i in arr && comparer(arr[i], val) ) {
            return i;
        }
    }
    return -1;
}
Read More
Labels:,, | 0 comments

Generate All Possible Permutations For Given Collection Of Items Using JavaScript

| Posted by

Problem

Given a collection of numbers, return all possible permutations.

Example

[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

JavaScript Code

function permute(num) {
    var result = [];
 
    //start from an empty list
    result.push([]);
 
    for (var i = 0; i < num.length; i++) {
        //list of list in current iteration of the array num
        var current = [];
 
        for (var k=0;k<result.length;k++) {
            var l = result[k];
            // # of locations to insert is largest index + 1
            for (var j = 0; j < l.length+1; j++) {
                // + add num[i] to different locations
                l.splice(j, 0, num[i]);
 
                var temp = JSON.parse(JSON.stringify(l));
                current.push(temp);                 
                
                // - remove num[i] add
                l.splice(j,1);
            }
        }
 
        result = JSON.parse(JSON.stringify(current));
    }
 
    return result;
}
Read More
Labels:,, | 0 comments

Get All Valid Sequences Of Course Schedule Using JavaScript

Thursday, 25 June 2015 | Posted by

Problem

This is also like before problem. Here we have to find all valid sequences out of given number of courses and prerequesites. 

Example

Given number of courses :: 2
Prerequesites :: [[0,1]]
Output :: [0,1]

Given number of courses :: 2
Prerequesites :: [[0,1][1,0]]
Output :: []

JavaScript Code

function findOrder(numCourses,  prerequisites) {
    if(prerequisites == null){
        return;
    }
 
    var len = prerequisites.length;
 
    //if there is no prerequisites, return a sequence of courses
    if(len == 0){
        var res = [];
        for(var m=0; m<numCourses; m++){
            res[m]=m;
        }
        return res;
    }
 
    //records the number of prerequisites each course (0,...,numCourses-1) requires
    var  pCounter = [];
    //initialize result
    var  result = [];
    for(var m=0; m<numCourses; m++){
        pCounter[m]=0;
        result[m]=0;
    }
    for(var i=0; i<len; i++){
        pCounter[prerequisites[i][0]]++;
    }
 
    //stores courses that have no prerequisites
    var queue = [];
    for(var i=0; i<numCourses; i++){
        if(pCounter[i]==0){
            queue.push(i);
        }
    }
 
    var numNoPre = queue.length;
 
    var j=0;
 
    while(queue.length!=0){
        var c = queue.shift();
        result[j++]=c;
 
        for(var i=0; i<len; i++){
            if(prerequisites[i][1]==c){
                pCounter[prerequisites[i][0]]--;
                if(pCounter[prerequisites[i][0]]==0){
                    queue.push(prerequisites[i][0]);
                    numNoPre++;
                }
            }
 
        }
    }
 
    //return result
    if(numNoPre==numCourses){
        return result;
    }else{
        return [];
    }
}

console.log(findOrder(2, [[1,0]]));
Read More
Labels:,, | 1 comments

Solve Course Schedule Graph Using JavaScript

Wednesday, 24 June 2015 | Posted by

Problem

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Examples

Given 2 and [[1,0]], there are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Given 2 and [[1,0],[0,1]], there are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

JavaScript Code

function canFinish(numCourses, prerequisites) {
    if(prerequisites == null){
        return;
    }
 
    var len = prerequisites.length;
 
    if(numCourses == 0 || len == 0){
        return true;
    }
 
    // counter for number of prerequisites
    var pCounter = [];
    for(var i=0; i<numCourses; i++){
        pCounter[i] = 0;
    }
    for(var i=0; i<len; i++){
        pCounter[prerequisites[i][0]]++;
    }
 
    //store courses that have no prerequisites
    var queue = [];
    for(var i=0; i<numCourses; i++){
        if(pCounter[i]==0){
            queue.push(i);
        }
    }
 
    // number of courses that have no prerequisites
    var numNoPre = queue.length;
 
    while(queue.length != 0){
        var top = queue.shift();
        for(var i=0; i<len; i++){
            // if a course's prerequisite can be satisfied by a course in queue
            if(prerequisites[i][1]==top){
                pCounter[prerequisites[i][0]]--;
                if(pCounter[prerequisites[i][0]]==0){
                    numNoPre++;
                    queue.push(prerequisites[i][0]);
                }
            }
        }
    }
 
    return numNoPre == numCourses;
}

console.log(canFinish(2, [[1,0],[0,1]]));
Read More
Labels:,, | 0 comments

Clone Graph Using JavaScript

| Posted by

Problem

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

JavaScript Code

function UndirectedGraphNode(value, nebrs) {
    this.val = value;
    if(nebrs != null) {
        this.neighbors = nebrs; 
    } else {
        this.neighbors = [];
    }
    this.visited = false;
}

UndirectedGraphNode.prototype = {
        constructor: UndirectedGraphNode
}

function cloneGraph(node) {
    if(node == null)
        return null;

    var queue = [];
    var map = {};

    var newHead = new UndirectedGraphNode(node.val, node.neighbors);

    queue.push(node);
    map[node.val] = newHead;

    while(queue.length != 0){
        var curr = queue.shift();
        var currNeighbors = curr.neighbors; 

        for(var aNeighbor in currNeighbors){
            if(map[aNeighbor.val]==null){
                var copy = new UndirectedGraphNode(node.val, node.neighbors);
                map[aNeighbor.val] = copy;
                map[curr.val].neighbors.push(copy);
                queue.push(aNeighbor);
            }else{
                map[curr.val].neighbors.push(map[aNeighbor.val]);
            }
        }

    }
    return newHead;
}
Read More
Labels:,, | 4 comments

Find Minimum Path Sum Of Matrix Using JavaScript

Saturday, 20 June 2015 | Posted by

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

JavaScript Code

function minPathSum(grid) {
    if(grid == null || grid.length==0)
        return 0;
 
    var m = grid.length;
    var n = grid[0].length;
 
    var dp = [];
    for(var i=0;i<m;i++) {
        var temp = [];
        for(var j=0;j<n;j++) {
            temp.push(0);
        }   
        dp.push(temp);
    }
    dp[0][0] = grid[0][0];
    
    // initialize top row
    for(var i=1; i<n; i++){
        dp[0][i] = dp[0][i-1] + grid[0][i];
    }
    
    // initialize left column
    for(var j=1; j<m; j++){
        dp[j][0] = dp[j-1][0] + grid[j][0];
    }
    
    // fill up the dp table
    for(var i=1; i<m; i++){
        for(var j=1; j<n; j++){
            if(dp[i-1][j] > dp[i][j-1]){
                dp[i][j] = dp[i][j-1] + grid[i][j];
            }else{
                dp[i][j] = dp[i-1][j] + grid[i][j];
            }
        }
    }
    
    return dp[m-1][n-1];
}
Read More
Labels:,, | 2 comments
Subscribe to: Posts (Atom)

Blogroll

Popular Posts