1-D Dynamic Programming

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?

There are n piles of stones arranged in a row. The ith pile has stones[i] stones. A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles. Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

You have n dice, and each die has k faces numbered from 1 to k. Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice, so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.

We have n chips, where the position of the ith chip is position[i]. We need to move all the chips to the same position. In one step, we can change the position of the ith chip from position[i] to: position[i] + 2 or position[i] - 2 with cost = 0. position[i] + 1 or position[i] - 1 with cost = 1. Return the minimum cost needed to move all the chips to the same position.

You are given an even number of people numPeople that stand around a circle and each person shakes hands with someone else so that there are numPeople / 2 handshakes total. Return the number of ways these handshakes could occur such that none of the handshakes cross. Since the answer could be very large, return it modulo 109 + 7.

Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be: 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1]) 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1]) 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j]) 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j]) Notice that there could be some signs on the cells of the grid that point outside the grid. You will initially start at the upper left cell (0, 0).

You are given two groups of points where the first group has size1 points, the second group has size2 points, and size1 >= size2. The cost of the connection between any two points are given in an size1 x size2 matrix where cost[i][j] is the cost of connecting point i of the first group and point j of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group. Return the minimum cost it takes to connect the two groups.

Given n points on a 1-D plane, where the ith point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints. Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 109 + 7.

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it. For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left. Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 109 + 7.

A generic microwave supports cooking times for: at least 1 second. at most 99 minutes and 99 seconds. To set the cooking time, you push at most four digits. The microwave normalizes what you push as four digits by prepending zeroes. It interprets the first two digits as the minutes and the last two digits as the seconds. It then adds them up as the cooking time. For example, You push 9 5 4 (three digits). It is normalized as 0954 and interpreted as 9 minutes and 54 seconds. You push 0 0 0 8 (four digits). It is interpreted as 0 minutes and 8 seconds. You push 8 0 9 0. It is interpreted as 80 minutes and 90 seconds. You push 8 1 3 0. It is interpreted as 81 minutes and 30 seconds.

You are given an integer total indicating the amount of money you have. You are also given two integers cost1 and cost2 indicating the price of a pen and pencil respectively. You can spend part or all of your money to buy multiple quantities (or none) of each kind of writing utensil. Return the number of distinct ways you can buy some number of pens and pencils.

You are given an integer money denoting the amount of money (in dollars) that you have and another integer children denoting the number of children that you must distribute the money to. You have to distribute the money according to the following rules: All money must be distributed. Everyone must receive at least 1 dollar. Nobody receives 4 dollars. Return the maximum number of children who may receive exactly 8 dollars if you distribute the money according to the aforementioned rules. If there is no way to distribute the money, return -1.

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Given a string s, return the longest palindromic substring in s.

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1 " 'B' -> "2 " ... 'Z' -> "26 " To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106 " can be mapped into: "AAJF " with the grouping (1 1 10 6) "KJF " with the grouping (11 10 6) Note that the grouping (1 11 06) is invalid because "06 " cannot be mapped into 'F' since "6 " is different from "06 ". Given a string s containing only digits, return the number of ways to decode it. The test cases are generated so that the answer fits in a 32-bit integer.

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.

Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

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

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.