Problem 1483. Number of paths on a grid

Created by G K

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Consider a grid formed by n vertices vertically down, and m vertices horizontally right. Your starting point is at the top left vertex. Your destination is the bottom right vertex. You are permitted at each vertex to choose to move down or right, that is in the direction towards the destination. You are not to move on what constitutes a back step like moving left or up. If you hit the bottom boundary, or right boundary take it to be given there is only 1 way to the destination, that is following along the boundary.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Ex: in a 2x2 grid there are two ways. One way: First down, then right. The other way: First right, then down.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>4x3 has 10 ways</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>6x5 has 126 ways</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>This problem can be solved using dynamic programming but there are other methods too.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Problem 7) Prev:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1482\"><w:r><w:t>1482</w:t></w:r></w:hyperlink><w:r><w:t> Next:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1484\"><w:r><w:t>1484</w:t></w:r></w:hyperlink></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: normal; text-decoration: none; white-space: normal; "><div style="display: block; min-width: 0px; padding-top: 0px; transform-origin: 332px 148.5px; vertical-align: baseline; perspective-origin: 332px 148.5px; "><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 63px; white-space: pre-wrap; perspective-origin: 309px 63px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">Consider a grid formed by n vertices vertically down, and m vertices horizontally right. Your starting point is at the top left vertex. Your destination is the bottom right vertex. You are permitted at each vertex to choose to move down or right, that is in the direction towards the destination. You are not to move on what constitutes a back step like moving left or up. If you hit the bottom boundary, or right boundary take it to be given there is only 1 way to the destination, that is following along the boundary.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 21px; white-space: pre-wrap; perspective-origin: 309px 21px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">Ex: in a 2x2 grid there are two ways. One way: First down, then right. The other way: First right, then down.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 10.5px; white-space: pre-wrap; perspective-origin: 309px 10.5px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">4x3 has 10 ways</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 10.5px; white-space: pre-wrap; perspective-origin: 309px 10.5px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">6x5 has 126 ways</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 10.5px; white-space: pre-wrap; perspective-origin: 309px 10.5px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">This problem can be solved using dynamic programming but there are other methods too.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 10.5px; white-space: pre-wrap; perspective-origin: 309px 10.5px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">Problem 7) Prev:</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style=""> </span></span><a target='_blank' href = "http://www.mathworks.com/matlabcentral/cody/problems/1482"><span style=""><span style="">1482</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style=""> Next:</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style=""> </span></span><a target='_blank' href = "http://www.mathworks.com/matlabcentral/cody/problems/1484"><span style=""><span style="">1484</span></span></a></div></div></div>

Solve

Solution Stats

147 Solutions
65 Solvers

Last Solution submitted on Jan 29, 2023

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Tim on 2 May 2013

It would be more elegant to define the solution for the 1x1 case as 1 rather than 0.

G K on 11 May 2013

agree, but will leave as so, so as to not affect submitted solutions.

Rafael S.T. Vieira on 20 Jul 2020

I disagree with the base case. A 1x1 matrix has 1 path. And, the empty matrix has no path (zero).

goc3 on 28 Sep 2020

The first test case has been changed from 0 to 1 without rescoring past solutions.

Tyler on 13 Jul 2022

Very interesting problem when you think about it.

Solution Comments

Solution 2088105

1 Comment

1 Comment

Jonathan on 10 Jan 2020

The first test case is incorrect. The null path (starting and ending at the same place) is a solution. The 1x1 case should have 1 solution.

Problem Recent Solvers65

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1483. Number of paths on a grid

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers65

Suggested Problems

More from this Author10

Problem Tags

Community Treasure Hunt

Problem 1483. Number of paths on a grid

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers65

Suggested Problems

More from this Author10

Problem Tags

Community Treasure Hunt

Players