# Coding Interviews: Dynamic Programming

Given a string s, partition s such that every substring of the partition is a palindrome.

Return *the ***minimum*** cuts needed for a palindrome partitioning of* s.

Given an integer array nums, return *the length of the longest ***strictly increasing subsequence**.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence **at most once**. Note that the path does not need to pass through the root.

The **path sum** of a path is the sum of the node's values in the path.

Given the root of a binary tree, return *the maximum ***path sum*** of any ***non-empty*** path*.

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

The matching should cover the **entire** input string (not partial).

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

There is a robot on an m x n grid. The robot is initially located at the **top-left corner** (i.e., grid[0][0]). The robot tries to move to the **bottom-right corner** (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

You are given an integer array nums, which contains **distinct** elements and an integer k.

A subset is called a **k-Free** subset if it contains **no** two elements with an absolute difference equal to k. Notice that the empty set is a **k-Free** subset.

Return *the number of ***k-Free*** subsets of *nums.