Unique Paths

Overview

Medium 2 solutions

Categories

MathDynamic ProgrammingCombinatorics

package array.iterative;

import java.util.Arrays;

public class UniquePaths {

    public int uniquePaths(int rows, int cols) {
        int[] prev = new int[cols];
        Arrays.fill(prev, 1);

        for (int row = 1; row < rows; row++)
            for (int col = 1; col < cols; col++)
                prev[col] += prev[col - 1];

        return prev[cols - 1];
    }

}

package com.eureka
package array.iterative

object UniquePaths:

  def uniquePaths(rows: Int, cols: Int): Int =
    val memo = Array.fill(cols)(1)

    for
      _   <- 1 until rows
      col <- 1 until cols
    do memo(col) += memo(col - 1)

    memo(cols - 1)