斐波那契数列

爬楼梯（70）

给定n个楼梯，你可以每次走一阶或两阶台阶，求一共有多少种走法

设有前i个台阶时的走法一共有dp[i]种，那么前i+1个台阶的走法就是最后一次走1阶的走法(dp[i])加上最后一阶走2阶(dp[i-1])的走法，即dp[i+1] = dp[i] + dp[i-1]，故状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2] 当i为0时，表示没有台阶，故只有不走这一种走法，故dp[0] = 1 当i为1时，表示只有一阶台阶，故只有走一阶这一种走法，故dp[1] = 1

强盗抢劫（198）

抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量

设抢劫一排前i户住户的最大收益为dp[i]，那么在抢劫第i+1家时强盗就应该考虑：我是否要抢劫这一家取决于这一家的收益k[i +1]加上前i-1家的最大收益dp[i - 1]，是否大于前i家的最大收益dp[i]，故状态转移方程为dp[i + 1] = biger{(k[i +1] + dp[i - 1]), dp[i]}，即 dp[i] = biger{(k[i] + dp[i - 2]), dp[i - 1]} 当i为0时，表示没有住户，故dp[0] = 0 当i为1时，表示只有一户住户，故dp[1] = k[1]

强盗在环形街区抢劫（213）

抢劫一圈住户，但是不能抢邻近的住户，求最大抢劫量

此题与上一题的区别就是住户的首尾不能都抢，即k[1]和k[n]是互斥的，那么我们就分别对没有第一户的住户群和没有最后一户的用户群进行抢劫，故状态转移方程如下 dp1[i] = biger{(k[i] + dp1[i - 2]), dp1[i - 1]}(i∈[2,n]) dp2[i] = biger{(k[i] + dp2[i - 2]), dp2[i - 1]}(i∈[1,n - 1]) res = biger(dp1[n], dp2[n - 1]) 边界条件同上

矩阵路径

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 **说明：**每次只能向下或者向右移动一步。

设dp[i][j]表示当行动到grid[i][j]时的最小路径，则dp[i][j]的上一步一定时表格的上(dp[i - 1][j])或左(dp[i][j - 1])，而为了使路径最小，dp[i][j]应该取本格的值grid[i][j]加上本格上(dp[i - 1][j])和左中较小(dp[i][j - 1])的值，故状态转移方程如下 dp[i][j] = grid[i][j] + smaller{(dp[i - 1][j]), (dp[i][j - 1])} 当i = 0，j = 0时，dp[i][j] = grid[i][j] 当i = 0, j ≠ 0时，dp[i][j] = dp[i][j - 1] 当i ≠ 0, j = 0时，dp[i][j] = dp[i - 1][j]

不同路径

一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？

设dp[i][j]表示行动到grid[i][j]处的最大路径数，那么当机器人位于grid[i][j]位置时，到达该位置的方式有两种：从上方来或者从左方来。所以dp[i][j]就应该时从上方来的路径数dp[i][j - 1]和从左方来的路径数dp[i - 1][j]的总和，故动态转移方程为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 当i = 0,j = 0时，表示位于网格左上角，故dp[0][0] = 1 当i = 0时，表示位于网格的第一行，机器人只能从左方来，故dp[0][j] = 1 同理，dp[i][0] = 1

分割整数

分割整数的最大乘积

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

设dp[i]表示正整数n拆分后的最大乘积。则dp[i]为max{k * dp[i - k]}(i∈[2,i / 2])，动态转移方程如下 dp[i] = max{k * dp[i - k], k * (i - k)} dp[1] = 0 dp[2] = 1

完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

设dp[i]表示和为i的完全平方数的最少数量， dp[i] = min{dp[i - k] + dp[k]}，k∈[1,i) 最小的完全平方数是1，故当i <= 1时，dp[i] = i 当k * k = i时，dp[i] = 1

解码方法（91）

给你一个只含数字的 **非空 **字符串 s ，请计算并返回解码方法的总数。解码规则如下 'A' -> 1 'B' -> 2 ... 'Z' -> 26 例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)

"KJF" ，将消息分组为 (11 10 6)

消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

设dp[i]表示前i个字母的组合数，则根据第i个字母和第i - 1个字母的情况，可分成以下几种情况

k[i]=0
k[i]∈[1,6]
1. k[i - 1]∈[1,2]
2. k[i - 1]不属于[1,2]
k[i]∈(6,9]
1. k[i - 1]=1
2. k[i - 1]≠1

对应的dp[i]的情况如下

dp[i] = dp[i - 2]
占位
1. dp[i] = dp[i - 1] + dp[i - 2]
2. dp[i] = dp[i - 1]
占位
1. dp[i] = dp[i - 1] + dp[i - 2]
2. dp[i] = dp[i - 1]

当i = 0时，dp[0] = 1 当i = 1时，dp[1] = 1

最长递增子序列

最长递增子序列（300）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

设dp[i]表示取nums[i]，并以nums[i]为子序列最大值的情况下，最长递增子序列的长度。那么dp[i]就是所有在它之前的递增子序列数量中最大的那个数量再加上nums[i]这个数，当前前提时这些递增子序列的最后一位要比nums[i]小。即max{dp[j] + 1}（j∈[0, i]）,故状态转移方程为 dp[i] = max{dp[j] + 1}（j ∈[0, i), nums[j] < nums[i]） 当i = 0时，dp[0]=1

最长数对链

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

首先将数对根据第二个数的大小进行排序，设dp[i]表示以k[i]为结尾的数对链的最大长度，则dp[i]为满足条件的数对链再加上k[i]这个数对，即 dp[i] = max{dp[j] + 1}（j∈[0,i)且k[i][0] > k[j][1]） 当i=0时，dp[0] = 1

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

设dp[i][j]表示字符串text1的前i个字符和字符串text2的前j个字符的最长公共子序列。那么对于dp[i + 1][j]，如果text1[i+1]和text2[j]相同，则dp[i+1][j]就应该时dp[i][j-1]再加上这个字符，即dp[i+1][j] = dp[i][j-1] + 1，如果text1[i+1]和text2[j]不同，则dp[i+1][j]就应该取dp[i][j]和dp[i+1][j-1]中较大的那个，故状态转移方程如下 dp[i][j] = dp[i - 1][j - 1] + 1（text1[i] = text2[j]） dp[i][j] = biger{dp[i - 1][j], dp[i][j - 1]}（text1[i] ≠ text2[j]） 当i=0时，表示text1的长度为0，故此时dp[0][j] = 0，同理dp[i][0] = 0

背包问题 // todo

分割等和子集（416）

给你一个 **只包含正整数 **的 **非空 **数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

设首先nums数组的总和为sum，那么如果sum/2不是整数的话一定不能被等和分割，否则sum/2能否由sum数组中的数组成即为所求。定义dp[i][j]表示取nums数组中的前i个值，是否能组成j。那么nums[i]取还是不取呢？如果取nums[i]，那么dp[i][j]就为dp[i - 1][j - nums[i]]，如果不取nums[i]，那么dp[i][j]就是dp[i - 1][j]，这两个值中任意一个值为true，则dp[i][j]就为true，故状态转移方程为 dp[i][j] = (dp[i - 1][j - nums[i]] | dp[i - 1][j]) 当j=0时，表示能否组成0，不取数组nums中的任意一个数即可，故dp[i][0] = true 当i=0时，表示取数组nums[0:i]，故dp[0][j]=false

目标和（494）

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

令nums的和是sum，那么sum - target即为nums数组中的负数之和neg的两倍，即sum - target = neg * 2。那么问题就被转换成了在整数数组nums中，取若干个数，使其达到neg的组合方式。当然如果sum - target不能被2整除的话，那么就不存在任何一种组合定义dp[i][j]表示在数组nums中取前i个数，使其等于j的组合方式的数量。当取nums[i]时，则dp[i][j] = dp[i - 1][j - nums[i]]，当不取nums[i]时，dp[i][j] = dp[i - 1][j]，故状态转移方程如下 dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j] 当j = 0时，表示目标和为0，只有不取任何一个数这一种组合方式，故dp[i][0]=1 当i = 0时，表示数组为空，故dp[0][j] = 0

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

设dp[i][j][k]表示取前i个字符串，使其满足j个0，k个1的最大子集长度。则取strs[i]时，dp[i][j][k] = dp[i - 1][j - ofM(strs[i])][k - ofN(strs[i])] + 1，不取strs[i]时，dp[i][j][k] = dp[i - 1][j][k]。故状态转移方程为 dp[i][j][k] = biger{(dp[i - 1][j - ofM(strs[i])][k - ofN(strs[i])] + 1)，dp[i - 1][j][k]}

零钱兑换（322）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

设dp[i]表示凑成总金额的最小硬币个数。对数组中的每个面额的硬币进行遍历，取所需硬币最少的。即dp[i] = min{dp[i - coins[j]]} + 1，故状态转义方程为 dp[i] = min{dp[i - coins[j]]} + 1 当i = 0时，表示总金额是0，那么就不需要硬币就可以凑成，故dp[0] = 0 当dp[amount] = 0时，表示初始值，即没有任何一种硬币组合能组成总金额，返回 -1

零钱兑换二

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。

设dp[i]表示凑成总金额i的组合数。对数组中的每个面额的硬币进行遍历，并添加这个组合。故状态转义方程为 dp[i] = sum{dp[i - coins[j]] } 当i=0时，dp[0] = 1

单词拆分（139）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

设dp[i]表示字符串s的前i个字母能否由字典中的单词构成。遍历字典中的每个单词，看s[0,j]能否由字典中的单词构成，以及s[j,i]是否是字典中的某个单词。则状态转移方程为 dp[i] = 连或{dp[i - len(wordDict[j])]&&contains(wordDict,s[j,i])} dp[0] = true

组合总数

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

设dp[i]表示达到目标i的组合数，对nums的每个数字依次遍历，dp[i] = sum{dp[i - nums[j]}

股票交易

最佳买卖股票交易时机含冷冻期（308）

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

这里注意，冷冻期指的是当天交易结束后的状态设dp[i][0]表示当前持有股票，dp[i][1]表示当前不持有股票，且不在冷冻期，dp[i][2]表示当前不持有股票但是在冷冻期（当天卖出了股票）。那么在第i天，如果持有股票，则股票可能是昨天就持有的，即dp[i - 1][0]，也可能是今天买的，如果是今天买的，那么昨天就不能是冷冻期，即dp[i - 1][1] - k[i]。如果不持有股票且在冷冻期，那么一定是今天卖出了股票，即dp[i - 1][0] + k[i]。如果不持有股票且不在冷冻期，那么前一天就不持有股票，即dp[i - 1][1]或dp[i - 1][2]。故状态转义方程如下 dp[i][0] = biger{dp[i - 1][0], dp[i - 1][1] - k[i]} dp[i][1] = dp[i - 1][0] + k[i] dp[i][2] = biger{dp[i - 1][1], dp[i - 1][2]} 第一天时，不持有股票的情况就是0，持有股票则为-k[i]

买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

设dp[i][0]表示第i天持有股票时的最大收益，dp[i][1]表示第i天不持有股票时的最大收益。那么在第i天，如果持有股票，这只股票可能是昨天就持有的，即dp[i - 1][0]，也可能是今天才买的，如果是今天买的，那昨天一定不持有股票，即dp[i - 1][1] - k[i]。如果不持有股票，那么可能是昨天就不持有，即dp[i - 1][1]，也可能是今天才卖出的，即dp[i - 1][0] + k[i] - fee。故状态转移方程如下 dp[i][0] = biger{dp[i - 1][0], dp[i - 1][1] - k[i]} dp[i][1] = biger{dp[i - 1][1], dp[i - 1][0] + k[i] - fee} 第一天时，不持有股票的情况为0，持有股票则为-k[i]

只能进行两次的股票交易

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

设buy[i][0]表示买过一次股票且持有的最大收益，buy[i][1]表示买过两次股票且持有的最大收益，sell[i][0]表示卖过一次股票且不持有股票的最大收益，sell[i][1]表示卖过两次股票且不持有股票的最大收益。第i天，buy[i][0]可能前一天就持有，即buy[i - 1][0]，也可能时当天购买的，即-k[i]，sell[i][0]可能时之前卖掉的，即sell[i - 1][0]，也可能是当天卖掉的，即buy[i - 1][0] + k[i]。buy[i][1]可能是之前买的，即buy[i - 1][1]，也可能是当天买的，即sell[i - 1][0] - k[i]。sell[i][1]可能是之前就卖掉了，即sell[i - 1][1]，也可能是当天卖掉的，即buy[i - 1][1] + k[i]，故状态转移方程如下 buy[i][0] = biger{-k[i], buy[i - 1][0]} sell[i][0] = biger{sell[i - 1][0], buy[i - 1][0] + k[i]} buy[i][1] = biger{sell[i - 1][0] - k[i], buy[i - 1][0]} sell[i][1] = biger{sell[i - 1][1], buy[i - 1][1] + k[i]} 第一天时，buy[i][0] = -k[i], buy[i][1] = -k[i],sell那俩是0

只能进行k次的股票交易

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

设buy[i][j]表示在第i天，进行过j次交易，且当前持有股票的最大收益，sell[i][j]表示在第i天，进行过j次交易，且当前不持有股票的最大收益。在第i天，若当前持有股票，则有可能是当天买的，即sell[i - 1][j - 1] - prices[i]，也可能是之前就持有的，即buy[i - 1][j]；若当前不持有股票，则有可能是当天卖出的，及buy[i - 1][j] + prices[i]，也可能是之前就卖了的，及sell[i - 1][j]，故状态转义方程如下 buy[i][j] = biger{buy[i - 1][j], sell[i - 1][j - 1] + prices[i]} sell[i][j] = biger{sell[i - 1][j], buy[i - 1][j] - prices[i]} 在第一天时，buy[i][0] = -k[i]，sell[i][0] = 0