## Monday, September 28, 2015

### LeetCode OJ - Unique Paths II

Problem:

Solution:

Unlike Unique Paths, this problem has no closed form solution. Instead, we will use the simple dynamic programming algorithm.

At each cell, we compute the number of ways to reach a certain cell. The initial case is trivial.

ways[0][0] = 1.

Next, we can reach a cell either from above our from left (if they exists), so we have these.

ways[row][col] = ways[row - 1][col] + ways[row][col -1] // Decay the number of zero if array index out of bound.

That's give the following dynamic programming algorithm.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/unique-paths-ii/

#include "LEET_UNIQUE_PATHS_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_UNIQUE_PATHS_II
{
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
int height = obstacleGrid.size();
if (height > 0)
{
int width = obstacleGrid[0].size();
if (width > 0)
{
for (int h = 0; h < height; h++)
{
}
for (int h = 0; h < height; h++)
{
for (int w = 0; w < width; w++)
{
if (obstacleGrid[h][w] == 1)
{
}
else
{
int above = h == 0 ? 0 : answer[h - 1][w];
int left = w == 0 ? 0 : answer[h][w - 1];
int bonus = (h == 0 && w == 0) ? 1 : 0;
answer[h][w] = above + left + bonus;
}
}
}
return answer[height - 1][width - 1];
}
}
return 0;
}
};
};

using namespace _LEET_UNIQUE_PATHS_II;

int LEET_UNIQUE_PATHS_II()
{
Solution solution;
vector<vector<int>> obstacleGrid;
obstacleGrid.resize(3);
obstacleGrid[0].push_back(0);
obstacleGrid[0].push_back(0);
obstacleGrid[0].push_back(0);
obstacleGrid[1].push_back(0);
obstacleGrid[1].push_back(1);
obstacleGrid[1].push_back(0);
obstacleGrid[2].push_back(0);
obstacleGrid[2].push_back(0);
obstacleGrid[2].push_back(0);
cout << solution.uniquePathsWithObstacles(obstacleGrid) << endl;
return 0;
}