# leetcode 动态规划（DP）

• 53. Maximum Subarray
• 62. Unique Paths
• 63. Unique Paths II
• 64. Minimum Path Sum
• 70. Climbing Stairs
• 72. Edit Distance
• 87. Scramble String
• 91 . Decode Ways
• 97. Interleaving String
• 115 Distinct Subsequences
• 120. Triangle
• 139. Word Break
• 140. Word Break II
• 152. Maximum Product Subarray
• 174 . Dungeon Game
• 198. House Robber
• 213 . House Robber II
• 221 . Maximal Square
• 712. Minimum ASCII Delete Sum for Two Strings
• 718. Maximum Length of Repeated Subarray
• 799. Champagne Tower
• 818. Race Car

### 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

C++

Python

《编程珠玑》里其实有讲过。 最大值要么在左边要么在中间，还有就是中间的情况

C++

### 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note:m and n will be at most 100.

1. 设dp[i][j]为到坐标为（i,j）的方法数，则有dp[i][j]= dp[i-1][j]+dp[i][j-1] 水~
2. 这是看了discuss里面，有人用数学方法做的。 orz 原文如下:
• It’s true that this can be solved with dynamic programming. But you can see that every path has exactly m – 1 horizontal moves and n – 1 vertical moves. So, to get a particular path, you need to choose where to put your m – 1 horizontal moves (or your n – 1 vertical moves) amongst the m + n – 2 total moves. That gives (m+n-2 choose m-1) paths (or (m+n-2 choose n-1), which is the same).

C++

Python方法1

Python 方法2

### 63. Unique Paths II

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

The total number of unique paths is 2.

Note:m and n will be at most 100.

• (i,j)为障碍物，则dp[i][j]=0
• (i,j)不为障碍物则 dp[i][j]= dp[i-1][j]+dp[i][j-1]

C++

Python

### 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

C++

Python

### 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

C++

Python

$$Q^n = \left[ \begin{matrix} f_{n+1} & f_{n} \\ f_{n} & f_{n-1} \\ \end{matrix} \right] \\ 初始值Q^1= \left[ \begin{matrix} 1 &1 \\ 1 & 0 \\ \end{matrix} \right] \\$$

\begin{alignat}{2}Q^k &= \left[ \begin{matrix} f_{k+1} & f_{k} \\ f_{k} & f_{k-1} \\ \end{matrix} \right] \end{alignat}

\begin{alignat}{2}Q^{k+1} &= \left[ \begin{matrix} f_{k+1} & f_{k} \\ f_{k} & f_{k-1} \\ \end{matrix} \right] \left[ \begin{matrix} 1 &1 \\ 1 & 0 \\ \end{matrix} \right] \\& = \left[ \begin{matrix} f_{k+1}+f_{k} &f_{k+1} \\ f_{k+1} & f_{k} \\ \end{matrix} \right] \\& = \left[ \begin{matrix} f_{k+2} &f_{k+1} \\ f_{k+1} & f_{k} \\ \end{matrix} \right] \end{alignat}

C++ 复杂度O(Logn)

### 72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

• if word[i] == word[j] ： dp[i][j] = dp[i-1][j-1]
• if word[i] != word[j] ： dp[i][j]  下面三个数的最小值+1：
• dp[i-1][j]   可以看为word1[i-1]然后插入一个字符（word2[j]),或者说删掉 word2[j]
• dp[i][j-1]   可以看为word2[j-1]然后插入一个数(word1[i])，或者说删掉 word1[i]
• dp[i-1][j-1] 把word1[i] 改为word2[j]，或者word2[j]改为word1[i]

C++

Python

Java

### 87. Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

• s1[0, i-1]和s2[0, i-1] 是否可以旋转得到，并且s1[i, n – 1]和s2[i, n- 1] 也要能旋转得到
• 或者s1[0, i – 1]和s2[n – i, n – 1] 是否可以旋转得到，并且s1[i, n- 1]和s2[0, n – i] 也要能旋转得到

C++

Python

### 91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”,
it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

• 若s[i] !=’0′ ,  dp[i] += dp[i-1]
• 若10 <= s[i-1,i] <=26 , dp[i] += dp[i-2]

C++

• 若s[i] !=’0′ ,
• dp[i] += dp[i-1]
• 若10 <= s[i-1,i] <=26 , dp[i] += dp[i-2]
• s[i] ==’0′ ,
• 看看是否能和前面的合并。不能就返回0，可以就是dp[i-2]

### 97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

• dp[i][j] = s3[i+j-1]==s1[i-1] && dp[i-1][j]  || s3[i+j-1]==s2[j-1] && dp[i][j-1];  (尝试用s1[i-1]去匹配，故应该是dp[i-1][j]，同理用s2[j-1]去匹配）

C++

Python

### 115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

• S[i]==T[j]:  dp[i][j] = dp[i-1][j] + dp[i-1][j-1]  两字符串相等，要么跳过不匹配，要么匹配
• S[i]!=T[j]:  dp[i][j]= dp[i-1][j] 不相等只能不匹配这个

• dp[i][0] = dp[i – 1][0] + (s[i] == t[0])  即t[0]可以被s表示的数量

C++

C++

Python

### 120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

• Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

C++

Python

### 139. Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

• dp[i+1]= true ( dp[j] =true && s[j,i]在字典中）

1A

### 140. Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Python

### 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

• f(k) = max( A[k] , f(k-1) * A[k], A[k], g(k-1) * A[k] )
• g(k) = min(A[k],   g(k-1) * A[k], A[k], f(k-1) * A[k] )

### 174. Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

 -2 (K) -3 3 -5 -10 1 10 30 -5 (P)

Notes:

• The knight’s health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

• dp[i][j]= max ( 1 ,   min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]   )

C++

Python

### 198. House Robber

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

• i选择，那么只能dp[i-2]+num[i]
• i不选，那么dp[i-1]

### 213. House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### 221. Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

For example, given the following matrix:

Return 4.

• if matrix[i][j]==’1′  dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
• else dp[i][j] = 0

Python

### 712. Minimum ASCII Delete Sum for Two Strings

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Example 2:

Note:

• 0 < s1.length, s2.length <= 1000.
• All elements of each string will have an ASCII value in [97, 122].

• s1[i] == s2[j] :    dp[i][j] = dp[i-1][j-1] + ascii(s1[i])
• s1[i] != s2[j] :     dp[i][j] = max(dp[i-1][j] , dp[i][j – 1] )

C++

Java

Python

### 718. Maximum Length of Repeated Subarray

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

• if A[i – 1] == B[j – 1]   dp[i][j] = dp[i – 1][j – 1] + 1
• A[i – 1] != B[j – 1]    dp[i][j] = 0

ans则为dp数组的最大值

Java

Java

Python

### 799. Champagne Tower

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row.  Each glass holds one cup (250ml) of champagne.

Then, some champagne is poured in the first glass at the top.  When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it.  When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on.  (A glass at the bottom row has it’s excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full.  After two cups of champagne are poured, the two glasses on the second row are half full.  After three cups of champagne are poured, those two cups become full – there are 3 full glasses total now.  After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)

Example 1:
Input: poured = 1, query_glass = 1, query_row = 1
Output: 0.0
Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:
Input: poured = 2, query_glass = 1, query_row = 1
Output: 0.5
Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Note:

poured will be in the range of [0, 10 ^ 9].
query_glass and query_row will be in the range of [0, 99].

• dp[i + 1][j] += dp[i][j]
• dp[i + 1][j + 1] += dp[i][j]

C++

Python

Python

### 818. Race Car

Your car starts at position 0 and speed +1 on an infinite number line.  (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction “A”, your car does the following: position += speed, speed *= 2.

When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1.  (Your position stays the same.)

For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:
Input:
target = 3
Output: 2
Explanation:
The shortest instruction sequence is “AA”.

Example 2:
Input:
target = 6
Output: 5
Explanation:
The shortest instruction sequence is “AAARA”.

Note:

• 1 <= target <= 10000.

DP,设dp[i]为到达i的最小步数。

• 先走到2^(k-1) – 1处(A^(k-1))，然后掉头，然后走A^x, 然后掉头，走dp[i – (2^(k -1) – 1)+ 2^(x) – 1]，所以总共为k-1 +  1 + x + 1 + dp[i – (2^(k -1) – 1)+ 2^(x) – 1]
• 走到2^k – 1，然后掉头，走dp[2^k -1 – i]  总共 k + 1+ dp[2^k – 1- target]

C++

Python