# LeetCode DP(上)

6 分钟读完

LeetCode上动态规则类题目有23个，其中

• Easy: 1
• Medium: 11
• Hard: 11

#1.Climbing Stairs re

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?

f(n) = f(n-2) + f(n-1)

#2.Triangle re

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

[
,
[3,4],
[6,5,7],
[4,1,8,3]
]

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.

path[i][j] = min(path[i - 1][j - 1], path[i - 1][j]) + triangle[i][j];

#3.Best Time to Buy and Sell Stock re

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

prices[i]表示股票在第i天的价格，你只能买一支股票，卖一支股票，问怎么才能获得最大收益？

• minPrice[i]表示第0天到第i的最低价格，maxProfit[i]表示前i天能获得的最大收益；
• minPrice[i] = min(minPrice[i-1], prices[i]);
• 那么prices[i] - minPrice[i]则为在第i天卖出的最大收益；
• maxProfit[i] = max(prices[i] - minPrice[i], maxProfit[i-1]); 下面是优化后的算法，仅使用O(1)的存储空间

#4.Minimum Path Sum re

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.

• minSum[i][j]表示(0,0)到(i,j)的最小路径和
• (0,0)到(i,j)的最小路径是从左边(i,j-1)过来到(i,j)，还是从上面(i-1, j)过来，取决于minSum。递推关系如下

minSum[i][j] = min(minSum[i - 1][j], minSum[i][j - 1]) + grid[i][j];

#5.Maximum Subarray re

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.

• maxSum[i] 表示0…i的最大连续子数组和(包括a[i]);
• 如果maxSum[i]>=0,
• 则maxSum[i+1] = maxSum[i] + a[i+1]
• 否则maxSum[i+1] = a[i+1]

#6.Maximum Product Subarray ref

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.

• positive[i]表示0…i最大连续正数乘积(包括i)
• negative[i]表示0…i最大负数连续乘积(包括i)

#7.Word Break ref

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”.

• vbreak[i]表示s[i]…s[end]是否可以break
• 如果s[i…end]在dict中，或者存在k使得s[i…k-1] in dict && vbreak[i+k] == true，那么vbreak[i]=true;

#8.Decode Ways ref

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]，有三种解码方式

`````` 1. 单独解码，除了'0'字符
2. 和前一个字符s[i-1]组合在一块解码，要求s[i-1]=='1' or '2'
3. 和后一个字符s[i+1]组合在一块解码，要求s[i]=='1' or '2'
``````

`````` way1[i] = way1[i-1]+way2[i-1]
way2[i] = way3[i-1]
way3[i] = way1[i-1]+way2[i-1]
``````