Unique Paths Solutions in C++

// Source : https://oj.leetcode.com/problems/unique-paths/
// Author : Hao Chen
// Date   : 2014-06-25



#ifdef CSTYLE

#include <stdio.h>
#include <stdlib.h>

void printMatrix(int*a, int m, int n)
{
    for (int i=0; i<m; i++){
        for (int j=0; j<n; j++){
            printf("%4d ", a[i*n+j]);
        }
        printf("\n");
    }
    printf("\n");
}

/*
 * Dynamic Programming
 *
 * We have a dp[i][j] represents  how many paths from [0][0] to hear. So, we have the following DP formuler:
 *
 *    dp[i][j] =  1  if i==0 || j==0        //the first row/column only have 1 uniqe path.
 *             =  dp[i-1][j] + dp[i][j-1]   //the path can be from my top cell and left cell.
 */

// using C style array
int uniquePaths(int m, int n) {
    int* matrix = new int[m*n];
    printMatrix(matrix, m, n);
    for (int i=0; i<m; i++){
        for (int j=0; j<n; j++){
            if(i==0 || j==0){
                matrix[i*n+j]=1;
            }else{
                matrix[i*n+j] = matrix[(i-1)*n+j] + matrix[i*n+j-1];
            }
        }
    } 
    printMatrix(matrix, m, n);
    int u = matrix[m*n-1];
    delete[] matrix;
    return u;
}

#else

#include <vector>
using namespace std;

// using C++ STL vector , the code is much easy to read
int uniquePaths(int m, int n) {
    vector< vector <int> >  dp (n, vector<int>(m, 1));
    for (int row=1; row<n; row++) {
        for (int col=1; col<m; col++) {
            dp[row][col] = dp[row-1][col] + dp[row][col-1];
        }
    }
    return dp[n-1][m-1];
}

#endif

int main(int argc, char** argv)
{
    int m=3, n=7;
    if( argc>2){
        m = atoi(argv[1]);
        n = atoi(argv[2]);
    }

    printf("uniquePaths=%d\n", uniquePaths(m,n));
    return  0;
}

#include <functional>
#include <vector>

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m > n) std::swap(m, n);
        if (m < 2) return m;
        std::vector<int> steps(n, 1);
        for (int i=1; i<m; ++i)
            for (int j=1; j<n; ++j)  
                steps[j] += steps[j-1];
        return steps[n-1];
    }
};

/// Source : https://leetcode.com/problems/unique-paths/
/// Author : liuyubobobo
/// Time   : 2019-04-02

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(m * n)
/// Space Complexity: O(m * n)
class Solution {

public:
    int uniquePaths(int m, int n) {

        vector<vector<int>> dp(m, vector<int>(n, 0));
        return dfs(m - 1, n - 1, dp);
    }

private:
    int dfs(int x, int y, vector<vector<int>>& dp){

        if(x == 0 || y == 0) return 1;
        if(dp[x][y]) return dp[x][y];

        int res = dfs(x - 1, y, dp) + dfs(x, y - 1, dp);
        return dp[x][y] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/unique-paths/
/// Author : liuyubobobo
/// Time   : 2019-04-02

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(m * n)
/// Space Complexity: O(m * n)
class Solution {
public:
    int uniquePaths(int m, int n) {

        vector<vector<int>> dp(m, vector<int>(n, 1));
        for(int i = 1; i < m; i ++)
            for(int j = 1; j < n; j ++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }
};


int main() {

    return 0;
}