C++ | Top - down + Bottom - Up | DP with explanation
Logic is same in both top-down and bottom-up, the only difference is in the way of traversing. \n\n1 in the grid represents  \' \ \'   and -1 in th grid represe
Logic is same in both top-down and bottom-up, the only difference is in the way of traversing. \n\n1 in the grid represents  \' \\ \'   and -1 in th grid represents  \' / \'   .\n\nWe can observe ball will get stuck in following 3 cases:\n\n* when slope formed by 1 and -1 are forming a V-shaped structure , i.e  \' \\/ \' \n* when last row index contains 1 , i.e \' \\| \'\n* when first row index contains -1 , i.e  \' |/ \'\n\nIf the curr grid[r][c] is 1 , check its adjacent left cell if it\'s 1 , move to the diagonal cell grid [r+1][c+1] else return -1\n\nIf the curr grid  is -1 , check if its adjacent right cell if it\'s -1 , move to diagonal cell grid[r+1][c-1] else return -1\n\nwhen r >= row.size() return its column number as ball has left the box.\n\n**Bottom - up**\n```\nclass Solution {\npublic:\n    vector<int> findBall(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n\t\t\n        vector<vector<int>>dp(m+1,vector<int>(n,-1));\n\t\t\n        for(int i = 0;i<n;i++){\n            dp[m][i] = i;\n        }\n\t\t\n        vector<int>res(n,0);\n\t\t\n        for(int i = m-1 ;i >= 0;i--){\n\t\t\n            for(int j = n-1;j>=0 ;j--){\n\t\t\t\n                if(grid[i][j]==1 && j+1<n && grid[i][j+1] != -1 ){\n\t\t\t\t\n                    dp[i][j] = dp[i+1][j+1];\n                }\n                if(grid[i][j] == -1 && j-1>=0 && grid[i][j-1] != 1){\n\t\t\t\t\n                    dp[i][j] = dp[i+1][j-1];\n                }\n\t\t\t\t\n                res[j] = dp[i][j];\n            }\n        }\n        \n        return res;\n    }\n};\n```\n\n**Top - down **\n```\nclass Solution {\npublic:\n    int recursion(vector<vector<int>>&grid, int &m , int &n , vector<vector<int>>&memo,int i , int j){\n        if(i>=m)return j;\n        \n        if(memo[i][j] != -2)return memo[i][j];\n        \n        int col = -1;\n        \n        if(grid[i][j] == 1 && j + 1 < n && grid[i][j+1] != -1){\n            \n            col = recursion(grid,m , n ,memo, i+1, j+1);\n            \n        }\n        if(grid[i][j] == -1 && j-1>=0 && grid[i][j-1] != 1){\n            \n            col = recursion(grid,m , n , memo, i+1, j-1);\n            \n        } \n        \n        return memo[i][j] = col;\n    }\n    vector<int> findBall(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n        \n        vector<int>res(n,0);\n        vector<vector<int>>memo(m,vector<int>(n,-2));\n        \n        for(int i = 0;i<n;i++){\n            \n            res[i] = recursion(grid,m,n,memo,0,i);\n            \n        }\n        \n        return res;\n    }\n};\n\n
['Dynamic Programming', 'Memoization', 'C', 'C++']