online advertising

Monday, September 21, 2015

LeetCode OJ - Unique Paths

Problem:

Please find the problem here.

Solution:

I have seen this problem so many time, typical dynamic programming solution would say the number of ways to reach a box is the sum of number of ways reaching its neighbor, then we figure this is simply the Pascal triangle, and therefore the solution is the binomial coefficients.

Code:

#include "stdafx.h"

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

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

using namespace std;

namespace _LEET_UNIQUE_PATHS
{
    class Solution
    {
    public:
        int uniquePaths(int m, int n)
        {
            if (m == 1 || n == 1)
            {
                return 1;
            }
            long long result = 1;
            m--;
            n--;
            int u = m + n;
            n = min(m, n); // be careful with the loop below - this minimum is required
            for (int v = 1; v <= n; v++, u--)
            {
                result *= u;
                result /= v;
            }
            return (int)result;
        }
    };
};

using namespace _LEET_UNIQUE_PATHS;

int LEET_UNIQUE_PATHS()
{
    Solution s;
    cout << s.uniquePaths(2, 100) << endl;
    return 0;
}

No comments :

Post a Comment