Explain Dynamic Programming and Other Techniques with Examples

• 1. Introduction
• 2. Longest Increasing Subsequence
  • 2.1 Problem Description
  • 2.2 Solution in JavaScript
• 3. Longest Common Subsequence
  • 3.1 Problem Description
  • 3.2 Solution in JavaScript
• 4. Longest Palindromic Substring
  • 4.1 Problem Description
  • 4.2 Solution in JavaScript
• 5. Longest Palindromic Subsequence
  • 5.1 Problem Description
  • 5.2 Solution in JavaScript
• 6. Maximum Product Subarray
  • 6.1 Problem Description
  • 6.2 Solution in JavaScript
• 7. Largest Rectangle in a Histogram
  • 7.1 Problem Description
  • 7.2 Solution in JavaScript
• 8. Egg Dropping Problem
  • 8.1 Problem Description
  • 8.2 Solution in JavaScript
• 9. Counting Bits
  • 9.1 Problem Description
  • 9.2 Solution in JavaScript
• 10. Perfect Squares
  • 10.1 Problem Description
  • 10.2 Solution in JavaScript
• 11. Unique Paths
  • Problem Description
  • Solution in JavaScript
• Conclusion

1. Introduction

In this article, we will dive into the world of dynamic programming, focusing on solving some programming challenges using also some other techniques. We will break down each problem, present different solutions in JavaScript, and provide a clear, concise explanation.

2. Longest Increasing Subsequence

2.1 Problem Description

The Longest Increasing Subsequence (LIS) problem is a classic programming challenge that requires finding the length of the longest subsequence of a given sequence, such that all elements of the subsequence are sorted in increasing order. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

For example, consider the sequence [10, 9, 2, 5, 3, 7, 101, 18]. The longest increasing subsequence here is [2, 3, 7, 101], and its length is 4.

2.2 Solution in JavaScript

To solve the LIS problem in JavaScript, we can use dynamic programming to break down the problem into smaller subproblems and solve them efficiently. Here's a step-by-step solution with detailed comments to help you understand the code:

function longestIncreasingSubsequence(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  
  // Initialize an array of length n, filled with 1s, as the minimum length of any LIS is 1
  const dp = Array(n).fill(1);
  
  // Iterate through the elements in the nums array
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      // Check if the current element is greater than the previous one
      if (nums[i] > nums[j]) {
        // If it is, update the dp array with the maximum length found so far
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  
  // Find the maximum length of the LIS by iterating through the dp array
  let maxLIS = dp[0];
  for (let i = 1; i < n; i++) {
    maxLIS = Math.max(maxLIS, dp[i]);
  }
  
  // Return the maximum length of the LIS
  return maxLIS;
}

To understand this solution, let's break down the key parts:

• We initialize an array called dp with the same length as the input array nums, and fill it with 1s. This array will store the length of the LIS ending at each index.
• We then use two nested loops to iterate through the elements in the nums array.
• If the current element is greater than the previous one, we update the dp array with the maximum length found so far.
• Finally, we find the maximum length of the LIS by iterating through the dp array and return it.

Time complexity and space complexity are as follows:

Time Complexity: O(n^2)

The time complexity of the solution is O(n^2) because we have two nested loops. The outer loop iterates over the elements in the input array nums and the inner loop iterates over the elements up to the current index in the outer loop. In the worst case, both loops will run n times, resulting in a total of n * n operations. Therefore, the time complexity is O(n^2).

Space Complexity: O(n)

The space complexity of the solution is O(n) because we are using an additional array dp to store the length of the LIS ending at each index. The size of the dp array is equal to the length of the input array nums, which is n. Apart from the dp array, we use a few variables, but their space consumption is constant and does not depend on the input size. Therefore, the space complexity is O(n).

If you ask is there a better and more efficient solution for the same challenge?

Yes, there is a better time complexity solution to the Longest Increasing Subsequence problem using a binary search algorithm. The time complexity for this approach is O(n*log(n)).

Here is the code and explanation for the better approach:

function longest_increasing_subsequence(nums) {
    let tails = [];
    tails[0] = nums[0];
    let length = 1;

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < tails[0]) {
            tails[0] = nums[i];
        } else if (nums[i] > tails[length - 1]) {
            tails[length++] = nums[i];
        } else {
            tails[lower_bound(tails, 0, length - 1, nums[i])] = nums[i];
        }
    }

    return length;
}

function lower_bound(arr, start, end, key) {
    while (start < end) {
        let mid = Math.floor((start + end) / 2);
        if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }

    return start;
}

In this approach, we maintain an array tails, which stores the minimum tail elements of all increasing subsequences we have seen so far. The tails array is sorted, and its length represents the length of the longest increasing subsequence. We iterate through the input array nums and, for each element:

1. If the element is smaller than the first element in tails, we replace the first element with the current element.
2. If the element is greater than the last element in tails, we append the element to the end of tails, increasing the length of the LIS by 1.
3. Otherwise, we find the smallest element in tails that is greater than or equal to the current element using the lower_bound function (binary search), and replace that element with the current element.

This approach is faster because, for each element in the input array, we perform a binary search operation that takes O(log(n)) time. Since there are n elements in the input array, the overall time complexity is O(n*log(n)).

The primary difference between the O(n^2) and O(nlog(n)) solutions is the technique used to update the subproblem solutions. The O(n^2) approach uses dynamic programming with a nested loop, whereas the O(nlog(n)) approach uses binary search to optimize the updates. The O(n*log(n)) solution is more efficient, especially for large input arrays.

3. Longest Common Subsequence

3.1 Problem Description

The Longest Common Subsequence (LCS) problem is a classic computer science problem that involves finding the longest subsequence common to two given sequences. A subsequence is a sequence that appears in the same order in both sequences but not necessarily consecutively. For example, the longest common subsequence of the strings "ABCD" and "ACDF" is "ACD".

3.2 Solution in JavaScript

To solve the Longest Common Subsequence problem, we will use dynamic programming. This approach allows us to break the problem down into smaller subproblems and solve them only once. Here's the JavaScript solution:

function longestCommonSubsequence(str1, str2) {
  const m = str1.length;
  const n = str2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

To understand the code, let's break it down step by step:

1. We first define the lengths of both input strings m and n.
2. We create a 2D array dp with dimensions (m + 1) x (n + 1) and initialize all elements to 0.
3. We loop through each character of both strings, comparing them at each step.
4. If the characters match, we increment the value in the dp array at the current position by adding 1 to the value at the diagonal position (up and left). This represents adding the current matched character to the LCS found so far.
5. If the characters don't match, we take the maximum value from either the cell above or the cell to the left. This represents considering the LCS found so far without the current characters.
6. After looping through both strings, the value in the bottom-right corner of the dp array represents the length of the Longest Common Subsequence.

The time complexity of this solution is O(m * n), where m and n are the lengths of the input strings. This is because we need to loop through each character in both strings and compare them.

The space complexity of the solution is also O(m * n) due to the 2D array dp that we create to store the intermediate results of the subproblems.

Let's have some optimization and do a code review.

The dynamic programming solution provided above has a time complexity of O(m * n), where m and n are the lengths of the input strings. While it may not be possible to significantly improve the time complexity for the general case, we can optimize the space complexity of the solution.

The current space complexity is also O(m * n) due to the 2D array dp. We can optimize this by using a rolling array and only keeping track of the current and previous rows. This reduces the space complexity to O(min(m, n)). Here's the optimized JavaScript solution:

function longestCommonSubsequence(str1, str2) {
  if (str1.length < str2.length) {
    [str1, str2] = [str2, str1];
  }

  const m = str1.length;
  const n = str2.length;
  const dp = Array.from({ length: 2 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i % 2][j] = 1 + dp[(i - 1) % 2][j - 1];
      } else {
        dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]);
      }
    }
  }

  return dp[m % 2][n];
}

In this optimized solution, we first swap str1 and str2 if str1 has a shorter length than str2. This ensures that str2 is always the shorter string, which reduces space complexity. Then, instead of initializing a 2D array with dimensions (m + 1) x (n + 1), we create a 2D array with dimensions 2 x (n + 1).

Inside the loops, we update the dp array using the modulo operator (%) to alternate between the two rows. This means that we only store the current row and the previous row, effectively reducing the space complexity to O(min(m, n)).

Please note that the time complexity remains O(m * n) because we still need to loop through each character in both strings and compare them. However, the space complexity is now optimized, making the solution more efficient in terms of memory usage.

4. Longest Palindromic Substring

4.1 Problem Description

The Longest Palindromic Substring problem involves finding the longest contiguous substring of a given string that reads the same forward and backward. For example, given the string "babad", the longest palindromic substring is either "bab" or "aba".

4.2 Solution in JavaScript

One way to solve this problem is by using dynamic programming. Here's the JavaScript solution:

function longestPalindromicSubstring(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(false));
  let maxLen = 1;
  let start = 0;

  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      if (len === 2) {
        dp[i][j] = s[i] === s[j];
      } else {
        dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
      }

      if (dp[i][j] && len > maxLen) {
        maxLen = len;
        start = i;
      }
    }
  }

  return s.substring(start, start + maxLen);
}

In this solution, we first create a 2D array dp, where dp[i][j] is true if the substring from index i to j is a palindrome. We initialize the diagonal elements of dp as true since single characters are always palindromes.

Next, we loop through the string using two nested loops. The outer loop iterates through the possible lengths of substrings (from 2 to the length of the input string), and the inner loop iterates through the starting positions of the substrings. If the current substring is a palindrome, we update the dp array and track the start position and maximum length of the palindrome.

Finally, we return the longest palindromic substring using the substring method.

Time complexity: O(n^2), where n is the length of the input string. This is because we need to loop through all possible substrings and check if they are palindromes.

Space complexity: O(n^2), due to the 2D array dp that stores the palindrome information for all possible substrings.

Dynamic programming is just one of the approaches to solve the Longest Palindromic Substring problem, and I provided it because it's a widely-used technique for such problems. However, there are other approaches to solve this problem, and I can provide an alternative solution using an expand-around-center technique.

The expand-around-center technique is based on the idea of iterating through the string and, for each character, expanding outwards to find the longest palindromic substring that includes that character. Here's the solution in JavaScript using this approach:

function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  return right - left - 1;
}

function longestPalindromicSubstring(s) {
  if (s == null || s.length < 1) return '';

  let start = 0;
  let end = 0;

  for (let i = 0; i < s.length; i++) {
    const len1 = expandAroundCenter(s, i, i);
    const len2 = expandAroundCenter(s, i, i + 1);
    const len = Math.max(len1, len2);

    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }

  return s.substring(start, end + 1);
}

In this solution, we first define a helper function expandAroundCenter, which returns the length of the longest palindromic substring centered around the given indices. Then, we iterate through the input string and call the helper function to find the longest palindromic substring for each character.

Time complexity: O(n^2), where n is the length of the input string. In the worst case, we need to expand around each character in the input string, which takes quadratic time.

Space complexity: O(1), as we are not using any additional data structures to store intermediate results, and the memory usage does not depend on the size of the input string.

This approach may have better performance than dynamic programming for some cases because it can skip some unnecessary checks when expanding around the center. However, both methods still have a time complexity of O(n^2).

So, is there a better time complexity then O(n^2)?

Yes, there is an algorithm called Manacher's Algorithm that solves the Longest Palindromic Substring problem with a better time complexity of O(n). This algorithm is specifically designed to find the longest palindromic substring more efficiently by avoiding redundant checks and utilizing previously calculated information.

Here's the implementation of Manacher's Algorithm in JavaScript:

function manachersAlgorithm(s) {
  if (s == null || s.length === 0) return '';

  let modifiedString = '#';
  for (let i = 0; i < s.length; i++) {
    modifiedString += s[i] + '#';
  }

  const p = new Array(modifiedString.length).fill(0);
  let center = 0;
  let rightBoundary = 0;
  let maxLen = 0;
  let maxLenCenter = 0;

  for (let i = 1; i < modifiedString.length - 1; i++) {
    if (rightBoundary > i) {
      const mirror = 2 * center - i;
      p[i] = Math.min(rightBoundary - i, p[mirror]);
    }

    while (
      i + p[i] + 1 < modifiedString.length &&
      i - p[i] - 1 >= 0 &&
      modifiedString[i + p[i] + 1] === modifiedString[i - p[i] - 1]
    ) {
      p[i]++;
    }

    if (i + p[i] > rightBoundary) {
      center = i;
      rightBoundary = i + p[i];
    }

    if (p[i] > maxLen) {
      maxLen = p[i];
      maxLenCenter = i;
    }
  }

  const start = Math.floor((maxLenCenter - maxLen) / 2);
  return s.substring(start, start + maxLen);
}

In this algorithm, we first modify the input string by adding special characters (e.g., '#') between the original characters. This helps to handle even- and odd-length palindromes uniformly. Then, we use an array p to store the palindrome radius centered at each character of the modified string.

We iterate through the modified string and update the palindrome radius for each character while keeping track of the right boundary of the current palindrome and its center. We utilize the information about the previously calculated palindrome radius to skip some redundant checks and avoid extra work.

Time complexity: O(n), where n is the length of the input string. Manacher's Algorithm performs a linear number of operations by avoiding redundant checks and utilizing previously calculated information.

Space complexity: O(n), as we store the palindrome radius for each character of the modified string, which has a length proportional to the input string length.

Manacher's Algorithm provides a faster solution to the Longest Palindromic Substring problem compared to the dynamic programming and expand-around-center methods, which have a time complexity of O(n^2).

5. Longest Palindromic Subsequence

5.1 Problem Description

In this problem, we need to find the longest palindromic subsequence in a given string. Unlike the substring, a subsequence doesn't require the characters to be contiguous in the original string, but they must maintain their order.

5.2 Solution in JavaScript

We can solve this problem using dynamic programming. The idea is to create a 2D table to store the lengths of the longest palindromic subsequences of the substrings.

function longestPalindromicSubsequence(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[0][n - 1];
}

In this solution, we first initialize a 2D table dp of size n x n, where n is the length of the input string. We set the diagonal elements of dp to 1 since a single character is always a palindrome.

We then iterate through the table, filling it with the lengths of the longest palindromic subsequences for all substrings. If the characters at the beginning and end of the substring are the same, we add 2 to the value of the inner substring. Otherwise, we set the value to the maximum of the previous row and previous column.

The final answer is stored in the top-right cell of the table, dp[0][n - 1].

Time complexity: O(n^2), where n is the length of the input string. We need to fill the 2D table of size n x n.

Space complexity: O(n^2), as we store the lengths of the longest palindromic subsequences in the dp table.

Our usual question: Is there a better time or space complexity than O(n^2)?

There isn't a significantly better time complexity than O(n^2) for the Longest Palindromic Subsequence problem using dynamic programming. However, you can optimize the space complexity using a rolling array or two 1D arrays instead of a 2D array.

Here's an optimized solution with a space complexity of O(n):

function longestPalindromicSubsequence(s) {
  const n = s.length;
  let prev = Array(n).fill(0);
  let curr = Array(n).fill(0);

  for (let i = n - 1; i >= 0; i--) {
    curr[i] = 1;
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j]) {
        curr[j] = prev[j - 1] + 2;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }
    [prev, curr] = [curr, prev];
  }

  return prev[n - 1];
}

In this solution, we use two 1D arrays, prev and curr, to represent the previous row and current row of the 2D dp table. This reduces the space complexity to O(n) while maintaining the same time complexity of O(n^2).

In summary, the time complexity remains O(n^2), but the space complexity is improved to O(n) using this optimized approach.

6. Maximum Product Subarray

6.1 Problem Description

The Maximum Product Subarray problem involves finding the contiguous subarray within a one-dimensional array of numbers that has the largest product. The input array may contain both positive and negative numbers.

6.2 Solution in JavaScript

To solve this problem, we can use dynamic programming. We keep track of the maximum and minimum product subarrays ending at each position, as the current number may be negative, which can turn the minimum product into the maximum product when multiplied.

Here's the solution in JavaScript:

function maxProductSubarray(nums) {
  const n = nums.length;
  let maxProd = nums[0];
  let minProd = nums[0];
  let maxSoFar = nums[0];

  for (let i = 1; i < n; i++) {
    let temp = maxProd;
    maxProd = Math.max(nums[i], Math.max(nums[i] * maxProd, nums[i] * minProd));
    minProd = Math.min(nums[i], Math.min(nums[i] * temp, nums[i] * minProd));
    maxSoFar = Math.max(maxSoFar, maxProd);
  }

  return maxSoFar;
}

In this solution, we iterate through the input array nums. At each position, we calculate the maximum and minimum product subarrays ending at that position. We update the overall maximum product maxSoFar whenever we find a larger product.

The time complexity of this solution is O(n) since we only make one pass through the input array. The space complexity is O(1) as we only use constant extra space to store the intermediate results.

In summary, this JavaScript solution has a time complexity of O(n) and space complexity of O(1) for the Maximum Product Subarray problem.

7. Largest Rectangle in a Histogram

7.1 Problem Description

The Largest Rectangle in a Histogram problem involves finding the largest rectangular area that can be formed within a histogram. A histogram is represented as an array of integers, where each element represents the height of a bar, and the width of each bar is 1.

7.2 Solution in JavaScript

To solve this problem, we can use a stack data structure to keep track of the indices of the bars in the histogram. This method helps us efficiently find the largest rectangle possible for each bar.

Here's the solution in JavaScript:

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length > 0 && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  return maxArea;
}

In this solution, we iterate through the input array heights. We maintain a stack to keep track of the indices of the bars in non-decreasing order of their heights. When we find a bar with a smaller height, we pop the elements from the stack and calculate the area of the rectangle that can be formed using the popped bar as the shortest one.

The time complexity of this solution is O(n) since we push and pop each element of the input array heights at most once. The space complexity is O(n) as we use a stack to store the indices of the bars.

In summary, this JavaScript solution has a time complexity of O(n) and space complexity of O(n) for the Largest Rectangle in a Histogram problem.

The solution provided above, with a time complexity of O(n) and space complexity of O(n), is considered optimal for the Largest Rectangle in a Histogram problem. It's unlikely that you would find a significantly more efficient algorithm in terms of time or space complexity.

The reason is that, in the worst case, you have to examine each bar in the histogram at least once to determine the largest rectangular area. This fact necessitates a lower-bound time complexity of O(n). The stack-based solution above takes advantage of this by maintaining a stack of indices, ensuring that each bar is only processed once.

8. Egg Dropping Problem

8.1 Problem Description

The Egg Dropping Problem is a classic problem in which you are given n eggs and a building with k floors. You need to determine the highest floor from which an egg can be dropped without breaking. The objective is to find the minimum number of attempts needed to find the solution.

8.2 Solution in JavaScript

The Egg Dropping Problem can be solved using dynamic programming. The idea is to use a 2D array dp, where dp[i][j] represents the minimum number of attempts required to find the highest floor from which an egg can be dropped without breaking, given i eggs and j floors.

function eggDrop(n, k) {
  const dp = Array(n + 1)
    .fill()
    .map(() => Array(k + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    dp[i][1] = 1;
    dp[i][0] = 0;
  }

  for (let j = 1; j <= k; j++) {
    dp[1][j] = j;
  }

  for (let i = 2; i <= n; i++) {
    for (let j = 2; j <= k; j++) {
      dp[i][j] = Infinity;
      for (let x = 1; x <= j; x++) {
        const res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
        dp[i][j] = Math.min(dp[i][j], res);
      }
    }
  }

  return dp[n][k];
}

The time complexity of this solution is O(n * k^2), and the space complexity is O(n * k). However, it is possible to optimize this solution further by using binary search instead of a linear search for the inner loop. This will reduce the time complexity to O(n * k * log(k)).

Overall, the Egg Dropping Problem is a challenging problem that can be solved using dynamic programming. By breaking down the problem into smaller subproblems and solving each subproblem only once, we can find the optimal solution and minimize the number of attempts needed to find the highest floor from which an egg can be dropped without breaking.

9. Counting Bits

9.1 Problem Description

Given a non-negative integer num, for every number i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

9.2 Solution in JavaScript

We can solve this problem by using dynamic programming. We can start by initializing an array of length num+1 with all values set to zero. Then, for each index i from 1 to num, we can update the value at i to be equal to the value at i divided by 2 plus the remainder of i divided by 2. This works because the number of 1's in the binary representation of a number i is equal to the number of 1's in the binary representation of i/2 plus 1 if i is odd, or 0 if i is even.

Here is the JavaScript code for this solution:

function countBits(num) {
  const dp = new Array(num + 1).fill(0);
  for (let i = 1; i <= num; i++) {
    dp[i] = dp[Math.floor(i / 2)] + (i % 2);
  }
  return dp;
}

The time complexity of this solution is O(n), where n is the input number num. This is because we loop through all numbers from 1 to num. The space complexity is also O(n), because we use an array of length num+1 to store the number of 1's for each number.

Overall, this is a simple and efficient solution to the counting bits problem, and it demonstrates the power of dynamic programming in solving algorithmic challenges.

10. Perfect Squares

10.1 Problem Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum up to n.

10.2 Solution in JavaScript

To solve this problem, we can use dynamic programming. We can create an array dp where dp[i] will store the least number of perfect square numbers that sum up to i.

Initially, we can set all the elements of the dp array to Infinity except the first element, which will be 0. This is because if n is 0, then there are no perfect squares that sum up to it, and if n is 1, then the least number of perfect squares that sum up to it is 1.

We can then iterate through all the numbers from 1 to n and for each number i, we can check all the perfect squares that are less than or equal to i. We can then update the value of dp[i] as the minimum of dp[i] and dp[i - j*j] + 1, where j*j is a perfect square less than or equal to i.

Finally, we can return the value of dp[n].

Here is the JavaScript code for the solution:

function numSquares(n) {
  const dp = Array(n + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }

  return dp[n];
}

The time complexity of this solution is O(n*sqrt(n)) and the space complexity is O(n).

11. Unique Paths

Problem Description

Suppose you have a m x n grid. You can move either down or right at any point in time. You are trying to reach the bottom-right corner of the grid. How many unique paths are there?

Solution in JavaScript

We can use dynamic programming to solve this problem. We start by initializing a 2D array dp of size m x n, where dp[i][j] represents the number of unique paths to reach the cell at (i,j).

We can fill in the first row and first column of the dp array with 1, because there is only one way to reach any cell in the first row or column. Then, for all other cells, the number of unique paths is the sum of the number of unique paths to reach the cell directly above and the cell directly to the left.

Finally, the value of dp[m-1][n-1] represents the number of unique paths to reach the bottom-right corner of the grid.

Here's the JavaScript code for the solution:

function uniquePaths(m, n) {
  const dp = Array(m).fill().map(() => Array(n).fill(1));
  
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  }
  
  return dp[m-1][n-1];
}

The time complexity of this solution is O(m * n), because we need to fill in each cell of the dp array exactly once. The space complexity is also O(m * n), because we are using a 2D array to store the values of dp.