# Path Finding using Dynamic Programming

I was trying to implement a dp + graph problem. After completing the solution I tried to compare it with solution in tutorial to figure out which one was better and to find a way to improve mine if I could. But I was not able to figure out which one is better, so please help. And if there is a way to improve my algorithm please tell me how I can do so.

## Solution in tutorial

Author's solution uses dynamic programming. Let dpi, j be the minimum time required to arrive at the vertex i, if we visit j vertices (including vertices 1 and i). We have a DAG (directed acyclic graph), so we can compute it recursively (and memory constraints were a bit strict in this problem, so it's better to use recursion to compute it). Let's store the transposed version of the graph: if we had an edge (u, v) in the input, we will store (v, u). Then our function calc(i, j), which will compute the answer for dpi, j, will be like that: the base of dynamic programming is dp1, 1 = 0, all other states are equal to «-1». If we call calc(i, j), then it will work like that: if the state we want to compute is incorrect (j < 0), we return a very large integer number (any number that is greater than 109, because T ≤ 109). If the answer for this state has already been calculated, then we return dpi, j (it is easy do determine: if dpi, j ≠  - 1, then it has already been calculated). Else we begin to calculate the state. Firstly, let's put INF (a number greater than 109) into dpi, j. Then look at all the edges beginning in i and try to update dpi, j with the value of calc(to, j - 1) + w (to is the vertex at the endpoint of current edge, w is the weight of this edge). If this value is less than dpi, j, then we update dpi, j and store the information that our last update in dpi, j was from the vertex to. If we try to go by path which doesn't end in the vertex 1, then we get a value which is greater than 109, that's because that the only value we didn't denote as  - 1 is dp1, 1. So, now we have our calc function, let's compute the answer. We will iterate on the number of vertices in the path from n to 1 in descending order, and if calc(n, i) ≤ T, then we have found the answer, now we iterate on the parent vertices we stored while calculating our dp, until we come to vertex 1 (it's important because some participants sent solutions that continued even past vertex 1!) and print the answer.

## My implementation of problem

#include<iostream>
using namespace std;

#define INT_MAX 5000

int getAns(int,int);
int n,a[INT_MAX][INT_MAX],dp[2][INT_MAX];
int main(){
int m,t,u,v,time;
cin>>n>>m>>t;
for(int i=0;i<m;i++){
cin>>u>>v>>time;
a[u][v]=time;
}
cout<<1+getAns(t,1)<<endl;
int i=1;
while(dp[1][i]!=0){
cout<<i<<" ";
i=dp[1][i];
}
cout<<i;
}

int getAns(int time,int curr){
if(time<0)
return 0;

for(int i=1;i<=n;i++){
if(a[curr][i]!=0&&a[curr][i]<=time){
int x=1+getAns(time-a[curr][i],i);
if(dp[0][curr]<x){
dp[0][curr]=x;
dp[1][curr]=i;
}
}
}
return dp[0][curr];
}

• Profiling: Just take some examples inputs and profile the runtime of both implementations. – MrSmith42 Jul 5 '17 at 9:37
• It is nice to use spaces. For example,for(int i=1;i<=n;i++){ becomes for (int i = 1; i <= n; i++) {. It improves readability. – Gabriel Jul 5 '17 at 13:23
• Side note: "and memory constraints were a bit strict in this problem, so it's better to use recursion to compute it" that's either cheating (if stack space isn't counted) or complete nonsense... – Daniel Jour Jul 5 '17 at 17:34