[Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)。有$n$个台阶，每次只能往上走一阶或两阶，问爬上顶层有多少种方法。[矩形填充](https://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6)。用$n$个$2\times{1}$的矩形去填充$2\times{n}$的区域，共有几种方法。

思路：第一题，每级阶梯只能由前一级或者前两级走过来，所以$dp[i]=dp[i-1]+dp[i-2]$。第二题，对于一个$2\times{i}$的区域，可以竖直填充一个$2\times{1}$变成一个$2\times{i-1}$的区域，或者横着填充两个$2\times{1}$的矩形变成$2\times{i-2}$的区域，所以$dp[i]=dp[i-1]+dp[i-2]$。


```python
def climbStairs(n: int) -> int:
    if n < 3:
        return n

    dp = [0]*n
    dp[0], dp[1] = 1, 2

    for i in range(2, n):
        dp[i] = dp[i-1]+dp[i-2]

    return dp[-1]
```

[Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)。一个数组表示$n$个台阶，每个数字表示跨越当前台阶的花费，每次跨越台阶可以选择跨一阶或跨两阶，求到达最高层的最小化费。起点可以在第一阶与第二阶中任选。

思路：易得每一层的状态只能有两种状态转换而来，前一层跨一层，前两层跨两层。所以设dp数组，其中$dp[i]$表示到达$i$层的最小花费，状态转移方程为：
$$
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
$$


```python
def minCostClimbingStairs(cost) -> int:
    n = len(cost)
    dp = [0]*(n+1)

    for i in range(2, n+1):
        dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])

    return dp[-1]
```




    6



[Word Break](https://leetcode.com/problems/word-break/)，**2019阿里、流利说手撕代码题**。给一个非空字符串$s$与一个字串集合$wordDict$，判断$s$能否拆分成若干个字典中的字串。

思路：设立dp数组，其中$dp[i]$表示以$i$位置结尾的字串是否可拆分。增加一个字符后，需要考察所有可能的切分点$j$，只有当切分点左边的字串可拆分并且切分点右边的字串在字典中时，切分点$j$才是合法的。


```python
def wordBreak(s: str, wordDict) -> bool:
    n = len(s)
    dp = [False]*(n+1)
    dp[0] = True

    for i in range(1, n+1):    # i比字串索引要大1
        for j in range(i):    # 切分点
            if dp[j] and s[j:i] in wordDict:
                dp[i] = True
                break

    return dp[-1]
```

[Coin Change](https://leetcode.com/problems/coin-change/)。给定若干面额的硬币，再给一个数值$num$，求组成$num$所需最少的硬币数。

思路：动态规划。设立dp数组，其中$dp[i]$表示对于数值$i$最少需要的硬币数，初始状态$dp[0]=0$，其他位置初始化为最大值。对于数值$i$与面值$denomination$，状态转移方程为：
$$
dp[i]=min(dp[i],dp[i-denomination]+1)
$$


```python
def coinChange(coins, amount: int) -> int:
    dp = [0x7FFFFFFF]*(amount+1)
    dp[0] = 0

    for i in range(1, amount+1):
        for val in coins:
            if val <= i:
                dp[i] = min(dp[i], dp[i-val]+1)

    return dp[-1] if dp[-1] != 0x7FFFFFFF else -1
```




    3



[Coin Change 2](https://leetcode.com/problems/coin-change-2/)。给定若干面额的硬币，再给一个数值，求组成$num$有几种方式。

思路：设立dp数组，其中$dp[i]$表示组成$i$有多少种方法。该题难点就在于怎么避免计算重复的答案，如$1+2=3$和$2+1=3$是重复答案。假设初始状态只有一种面额的硬币，那么状态转移方程就为：
$$
dp[val]=dp[val-denomination]+dp[val-2*denomination]+...
$$
即只有$val$能被$denomination$整除时才有解。然后再加入一种面额，状态转移方程不变。


```python
def change(amount: int, coins) -> int:
    n = len(coins)
    dp = [0]*(amount+1)
    dp[0] = 1

    for denomination in coins:    # 以增加面额的方式来考虑问题
        for val in range(denomination, amount+1):
            dp[val] += dp[val-denomination]

    return dp[-1]
```




    4



[Unique Paths](https://leetcode.com/problems/unique-paths/)。从一个矩形的左上方走到右下方有多少种不同的走法？只能往右或往下走。

思路：设立dp矩阵，其中$dp[row][col]$表示从左上方走到$(row,col)$的可能数。初始状态，首行跟首列的位置只能是$1$，状态转移方程为：
$$
dp[row][col]=dp[row-1][col]+dp[row][col-1]
$$


```python
def uniquePaths(m: int, n: int) -> int:
    dp = [[1]*n for _ in range(m)]
    for row in range(1, m):
        for col in range(1, n):
            dp[row][col] = dp[row-1][col]+dp[row][col-1]

    return dp[-1][-1]
```

[Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)。给一数组，求出其最长递增子序列的长度。

思路：设立一个dp数组，其中$dp[i]$表示以索引$i$结尾的字串最长子序列的长度，初始状态为$dp[i]=1$，因为任一单字符都可构成一个子序列。那么状态转移方程为：
$$
dp[i]=max(dp[i],dp[j_{1}]+1,dp[j_{2}]+1,...,dp[j_{k}]+1)
$$
其中$j$特指$nums[j]<nums[i]$的索引。注意该题的状态转移并不由之前的单个状态决定，而是需要遍历。


```python
def lengthOfLIS(self, nums: List[int]) -> int:
    if not nums:
        return 0
    n = len(nums)
    dp = [1]*n

    for i in range(1, n):
        for pre in range(i):
            if nums[pre] < nums[i]:
                dp[i] = max(dp[i], dp[pre]+1)

    return max(dp)
```




    4



[LCS](https://www.nowcoder.com/practice/c996bbb77dd447d681ec6907ccfb488a?tpId=49&&tqId=29348&rp=2&ru=/activity/oj&qru=/ta/2016test/question-ranking)。求最长公共子序列的长度。

思路：设立二维$dp$数组，其中$dp[i][j]$表示$s1$的前$i$位与$s2$的前$j$位LCS的长度。易得$dp$的初始状态为首行首列都为$0$，状态转移方程为：
$$
\begin{align}
dp[i][j]=
\begin{cases}
dp[i-1][j-1]+1 & ,s1[i]=s2[j] \\
max(dp[i-1][j],dp[i][j-1]) & ,s1[i]\ne{s2[j]} \\
\end{cases}
\end{align}
$$


```python
def LCS(a, b):
    len_a, len_b = len(a), len(b)
    dp = [[0]*(len_b+1) for _ in range(len_a+1)]

    for i in range(1, len_a+1):
        for j in range(1, len_b+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[-1][-1]
```




    4



[Jump Game II](https://leetcode.com/problems/jump-game-ii/)。给一数组，每个数字表示在当前位置可以前进的最大距离。现在保证从起点出发一定可以到达终点，求最小的步数。

思路：设立dp数组，其中$dp[i]$表示到达$i$位置的最小步数。那么可以根据$dp[i]$与$nums[i]$的值去更新后面dp的值。思路应该没错，但是超时了，时间复杂度为$O(n^{2})$。


```python
def jump(nums) -> int:
    n = len(nums)
    dp = [0x7FFFFFFF]*n
    dp[0] = 0

    for idx, num in enumerate(nums):
        for offset in range(1, num+1):
            pos = idx+offset if idx+offset < n else n-1
            dp[pos] = min(dp[pos], dp[idx]+1)

    return dp[-1]
```

[Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)。给一数组表示一只股票的历史价格，允许买卖两次，求最大利润。

思路：设立dp数组，其中$dp[i][j]$表示在允许交易$i$次的条件下第$j$天的最大利润。同时对每一个不同$i$的配置，维护一个余额变量```balance```，表示持股状态下的最大余额。易得初始状态为$dp[0][j]=0$，$balance=-prices[0]$，两者的状态转移方程为：
$$
\left\{
\begin{align}
dp[i][j]&=max(dp[i][j-1],balance+prices[j]) \\
balance&=max(balance,dp[i-1][j-1]-prices[j]) \\
\end{align}
\right.
$$


```python
def maxProfit(prices) -> int:
    if len(prices) < 2:
        return 0

    n = len(prices)
    dp = [[0]*n for _ in range(2+1)]

    for i in range(1, 3):
        balance = -prices[0]
        for j in range(1, n):
            dp[i][j] = max(dp[i][j-1], balance+prices[j])    # 不操作或者卖掉
            balance = max(balance, dp[i-1][j-1]-prices[j])    # 不操作或者买进

    return dp[-1][-1]
```

[Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)。给一数组表示一只股票的历史价格，允许至多买卖$k$次，求最大利润。

思路：同上题。但是测试用例中有$k$特别大的情况。当$k$大于天数的一半时，相当于不限买卖次数，等同于[Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)。


```python
def maxProfit(k: int, prices) -> int:
    n = len(prices)
    if n < 2:
        return 0

    if k > (n//2):    # 同等于不限买卖次数的条件
        res = 0
        for idx in range(n-1):
            if prices[idx+1] > prices[idx]:
                res += prices[idx+1]-prices[idx]
        return res

    n = len(prices)
    dp = [[0]*n for _ in range(k+1)]

    for i in range(1, k+1):
        balance = -prices[0]
        for j in range(1, n):
            dp[i][j] = max(dp[i][j-1], balance+prices[j])
            balance = max(balance, dp[i-1][j-1]-prices[j])

    return dp[-1][-1]
```




    7



[Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)。给一数组表示一只股票的历史价格，不限定买卖次数，但是抛售之后需要隔一天才能再买，求最大利润。

思路：设两个dp数组，```hold```与```unhold```分别表示持股与不持股的最大利润，需要返回的是```unhold[-1]```。首先考虑初始状态，对于```hold```数组而言，```hold[0]=-price[0]```，即买入亏钱；```hold[1]=max(-prices[0],-prices[1])```，前两天选择价格最低的买入以获得最大利润或最小亏损；```unhold[0]=0```，因为第一天无法卖出；```unhold[1]=max(unhold[0],hold[0]+prices[1])```，不操作或者卖出第一天买入的股票。

状态转移方程为：
$$
\begin{align}
hold[i]&=max(hold[i-1],unhold[i-2]-prices[i]) \\
unhold[i]&=max(unhold[i-1],hold[i-1]+prices[i]) \\
\end{align}
$$
状态方程简而言之就是两种可能：无操作或者买入(卖出)，注意卖出之后买入需要隔天。


```python
def maxProfit(prices) -> int:
    n = len(prices)
    if n < 2:
        return 0

    hold, unhold = [0]*n, [0]*n

    hold[0] = -prices[0]
    hold[1] = max(-prices[0], -prices[1])
    unhold[1] = max(unhold[0], hold[0]+prices[1])

    for i in range(2, n):
        hold[i] = max(hold[i-1], unhold[i-2]-prices[i])
        unhold[i] = max(unhold[i-1], hold[i-1]+prices[i])

    return unhold[-1]
```

[Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)。

思路：同样设立两个dp数组，```hold```与```unhold```分别表示持股与不持股下的最大利润，最后返回```unhold[-1]```。初始状态，```hold[0]=-prices[0]```，```unhold[0]=0```，状态转移方程：
$$
\begin{align}
hold[i]&=max(hold[i-1],unhold[i-1]-prices[i]) \\
unhold[i]&=max(unhold[i-1],hold[i-1]+prices[i]-fee) \\
\end{align}
$$


```python
def maxProfit(prices, fee: int) -> int:
    n = len(prices)
    if n < 2:
        return 0

    hold, unhold = [0]*n, [0]*n
    hold[0] = -prices[0]

    for i in range(1, n):
        hold[i] = max(hold[i-1], unhold[i-1]-prices[i])
        unhold[i] = max(unhold[i-1], hold[i-1]+prices[i]-fee)

    return unhold[-1]
```




    8



[Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)。给一整形数组，找一连续子区间，返回该子区间的最大乘积。

思路：因为数组包含负数，所以要考虑负负得正的情况。维护两个$dp$数组```max_dp```和```min_dp```，其中$dp[i]$表示以$i$结尾且包含$i$的最大(小)乘积。状态转移方程为：
$$
\begin{align}
max\_dp[i]&=max(nums[i],min\_dp[i-1]*nums[i],max\_dp[i-1]*nums[i]) \\
min\_dp[i]&=min(nums[i],min\_dp[i-1]*nums[i],max\_dp[i-1]*nums[i]) \\
\end{align}
$$
因为最大乘积不一定包含最后一个数，所以返回的不是```dp[-1]```，而是需要随时记录最大乘积。注意到状态转移只取决于上一个位置，所以不需要设置数组，只需要设置变量即可。


```python
def maxProduct(nums) -> int:
    if not nums:
        return 0
    n = len(nums)
    if n == 1:
        return nums[0]

    res = min_pre = max_pre = nums[0]

    for i in range(1, n):
        min_cur = min(nums[i], min_pre*nums[i], max_pre*nums[i])
        max_cur = max(nums[i], min_pre*nums[i], max_pre*nums[i])
        res = max(res, max_cur)
        min_pre, max_pre = min_cur, max_cur

    return res
```




    6



[01背包问题](https://www.acwing.com/problem/content/2/)。给出若干件物品的价值$v_{i}$跟重量$w_{i}$，现有一个负重量为$W$的背包，求能得到的最大价值。

思路：经典DP问题。设立一个二维$dp$矩阵，其中$dp[i][j]$表示在有$j$负重量的条件下考虑前$i$件物品能得到的最大利润。易得初始状态为$dp[0][0]=0$，然后推状态转移方程。新增一个物品时，有两种决定：拿或不拿。不拿的情况下，dp值不变，$dp[i][j]=dp[i-1][j]$；拿的话，势必要给物品先腾地方，$dp[i][j]=dp[i-1][j-w[i]]+v[i]$。那么状态转移方程就为：
$$
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
$$


```python
def Knapsack(v, w, W):
    v.insert(0, 0)    # 保持idx一致，为第0件物品添加体积跟价值
    w.insert(0, 0)
    dp = [[0]*(W+1) for _ in range(N+1)]

    for i in range(1, N+1):    # 第i件物品
        for j in range(W+1):
            dp[i][j] = dp[i-1][j]    # 不拿

            if j >= w[i]:    # 负重量允许的情况下才能拿
                dp[i][j] = max(dp[i][j],
                               dp[i-1][j-w[i]]+v[i])

    return dp[-1][-1]
```

[完全背包问题](https://www.acwing.com/problem/content/3/)。现有不限量的$N$种物品，给出每种物品的价值$v$与重量$w$，还有一个负重量为$W$的背包，求能带走的最大价值。

思路：虽然题意指出每种物品不限量，但因为背包负重量是有限的，所以实际上所能拿的每种物品也是有限的。设$j$为递推时的背包负重量，那第$i$件物品的最大数量上限为$j//w[i]$。所以该题只需要在01背包问题上面加一重循环即可。


```python
def Knapsack(v, w, W):
    v.insert(0, 0)
    w.insert(0, 0)
    dp = [[0]*(W+1) for _ in range(N+1)]

    for i in range(1, N+1):
        for j in range(W+1):
            dp[i][j] = dp[i-1][j]

            max_cnt = j//w[i]
            for k in range(max_cnt+1):
                dp[i][j] = max(dp[i][j],
                               dp[i-1][j-k*w[i]]+k*v[i])

    return dp[-1][-1]
```

[Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)。给一个$m\times{n}$的矩阵，以左上角为起点，每次只能向下或向右移动，求最小路径和。

思路：典型的动态规划。设立dp数组，其中$dp[i][j]$表示走到$(i,j)$位置时的最小路径和。每一个位置只能由两个状态变换而来，上边和左边，所以状态转移方程为：

$$
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+nums[i][j]
$$


```python
def minPathSum(grid) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0]*cols for _ in range(rows)]

    # 首行首列需特殊处理
    dp[0][0] = grid[0][0]
    for col in range(1, cols):
        dp[0][col] = dp[0][col-1]+grid[0][col]
    for row in range(1, rows):
        dp[row][0] = dp[row-1][0]+grid[row][0]

    for row in range(1, rows):
        for col in range(1, cols):
            dp[row][col] = min(dp[row-1][col],
                               dp[row][col-1])+grid[row][col]

    return dp[-1][-1]
```




    7



[Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)。给一无重复元素的正整数数组$nums$与一个目标值$target$，数组中的数字可用无限次，求有多少种组合方式使得取出的数字求和等于$target$。

思路：设dp数组，其中$dp[i]$表示求和等于$i$的方式有多少种，那么状态转移方程为：
$$
\begin{align}
dp[i]&=dp[i-nums[0]]+dp[i-nums[1]]+\cdots+dp[i-nums[n]] \\
&=\sum_{j=1}^{n}{dp[i-nums[j]]} \\
\end{align}
$$
当然，$i-nums[j]$必须大于$0$才合法。


```python
def combinationSum4(nums, target: int) -> int:
    dp = [0]*(target+1)
    dp[0] = 1

    for sub_target in range(1, target+1):
        for num in nums:
            if sub_target >= num:
                dp[sub_target] += dp[sub_target-num]

    return dp[-1]
```




    7



[House Robber](https://leetcode.com/problems/house-robber/)。一数组表示各房屋内的金钱，不能同时搜刮相邻的两个房子，问最多能偷到多少钱。

思路：设```dp[i]```为有$i$个房子时最多能偷到的钱。增加一个房子时，因为不能偷相邻的房子，所以如果要偷最后的房子，则倒数第二个房子就不能偷；如果投了倒数第二个房子，则最后一个房子就不能偷。状态转移方程为：
$$
dp[i]=max(dp[i-2]+house[i],dp[i-1])
$$


```python
def rob(nums) -> int:
    n = len(nums)
    if n == 0:
        return 0
    if n < 3:
        return max(nums)

    dp = [0]*n
    dp[0] = nums[0]
    dp[1] = max(nums[:2])

    for i in range(2, n):
        dp[i] = max(dp[i-2]+nums[i], dp[i-1])

    return dp[-1]
```

[Ugly Number II](https://leetcode.com/problems/ugly-number-ii/)。丑数的定义如下，因子只有$2$、$3$和$5$的正数，第一个丑数定义为$1$。求第$n$个丑数。

思路：丑数的因子只含$2$、$3$和$5$且第一个丑数为$1$，那么从$1$开始乘上这些因子即可得到丑数序列。关键在于避免得到重复丑数，设置三个指针$p_{2}$、$p_{3}$和$p_{5}$，分别代表$\times{2}$、$\times{3}$和$\times{5}$的位置，计算丑数的递推式为：
$$
dp[i]=\min(dp[p2]*2,dp[p3]*3,dp[p5]*5)
$$
$dp[i]$肯定是由三种运算中的一种得来的，要避免重复计算，还需要判断另外两种运算是否会得到一样的结果，如果是的话需要做处理。


```python
def nthUglyNumber(n: int) -> int:
    dp = [1]*n
    m2 = m3 = m5 = 0

    for i in range(1, n):
        cur_num = min(dp[m2]*2, dp[m3]*3, dp[m5]*5)
        dp[i] = cur_num

        if cur_num == dp[m2]*2:
            m2 += 1
        if cur_num == dp[m3]*3:
            m3 += 1
        if cur_num == dp[m5]*5:
            m5 += 1

    return dp[-1]
```

[Maximum Length of Repeated Subarray](https://leetcode.com/problems/maximum-length-of-repeated-subarray/)。给两个整数数组，求公共连续子数组的最大长度。

思路：设置dp矩阵，其中$dp[i][j]$表示以$i$结尾且包含$A[i]$的子数组与以$j$结尾且包含$B[j]$的子数组的公共子数组长度。易得状态转移方程为：
$$
\begin{align}
dp[i][j]=
\begin{cases}
0, & A[i]\ne{B[j]}\\
dp[i-1][j-1]+1, & A[i]=B[j]\\
\end{cases}
\end{align}
$$


```python
def findLength(A, B) -> int:
    len_a, len_b = len(A), len(B)
    dp = [[0]*len_b for _ in range(len_a)]
    res = 0

    for j in range(len_b):
        dp[0][j] = 1 if A[0] == B[j] else 0
        res = max(res, dp[0][j])
    for i in range(len_a):
        dp[i][0] = 1 if B[0] == A[i] else 0
        res = max(res, dp[i][0])

    for i in range(1, len_a):
        for j in range(1, len_b):
            if A[i] != B[j]:
                dp[i][j] == 0
            else:
                dp[i][j] = dp[i-1][j-1]+1
                res = max(res, dp[i][j])

    return res
```




    3



[Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)。构建Pascal(杨辉)三角。

思路：每行的元素数等于行标号，除了边界元素为$1$，其他元素全由上行相加得出。


```python
def generate(numRows: int):
    if numRows==0:
        return list()
    
    res = [[1]]
    for row in range(2, numRows+1):
        cur_row = [1]*row
        for col in range(1, row-1):
            cur_row[col] = res[-1][col-1]+res[-1][col]

        res.append(cur_row)

    return res
```

[Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/)。给一行索引，返回杨辉三角的特定一行，行索引从$0$开始。

思路：类似动态规划，只保存上一行即可。


```python
def getRow(rowIndex: int):
    if rowIndex==0:
        return [1]

    pre_row=[1]
    for row in range(2,rowIndex+2):
        cur_row=[1]*row
        for col in range(1,row-1):
            cur_row[col]=pre_row[col-1]+pre_row[col]

        pre_row=cur_row

    return pre_row
```




    [1, 2, 1]




```python

```

5816ba069ec53fb32fbb032e8c2008d86416ae79
ipynb
Jupyter Notebook
Algorithm/BlankBoard/.ipynb_checkpoints/DynamicProgramming-checkpoint.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
2019-03-07T03:19:54.000Z
2019-08-22T08:12:41.000Z
Algorithm/BlankBoard/.ipynb_checkpoints/DynamicProgramming-checkpoint.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
Algorithm/BlankBoard/.ipynb_checkpoints/DynamicProgramming-checkpoint.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
Qwen/Qwen-72B
1. YES
2. YES