如何找到从源到目的地的路径数，它在2d矩阵中加到给定的和k？(How to find the number of path from source to destination which adds upto to a given sum k in a 2d matrix?)

270 IT屋

In NxN matrix containing numbers and block ''x''.find the number of path from the source ''s'' to destination ''d'' which adds upto given sum ''k''. Use Dynamic programming to solve this.Move in down ,right and diagonal direction.

input:
--------------
k = 3

s 1 1
1 x 1
1 1 d

output = 2
--------------
k = 5

e 1 1 1

1 1 1 1

1 1 1 1

1 1 1 s

output = 20
-------------

k = 7

e 2 3

2 x 2

1 2 s

output = 1
-------------

What I have tried:

I have tried using recursion, as it will take more time complexity.

We are more than willing to help those that are stuck: but that doesn''t mean that we are here to do it all for you! We can''t do all the work, you are either getting paid for this, or it''s part of your grades and it wouldn''t be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn''t mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

Quote:
How to find the number of path from source to destination which adds upto to a given sum k in a 2d matrix?

This look like some homework, but your main effort is pasting the requirement.
What is the question?
Quote:
Use Dynamic programming to solve this.

You are given hint about how to do.

We are not doing your homework, if you want help, you need to show your work and explain problem.

To get you started, you can start with a brute force approach (trying every path 1 by 1), then refine.

-------- ------

k = 3

s 1 1

1 x 1

1 1 d

--------------

k = 5

\$ b \$是1 1 1

1 1 1 1

1 1 1 1

1 1 1 s

-------------

k = 7

e 2 3

2 x 2

1 2 s

-------------

Quote：