动态规划：

[图片上传失败...(image-a45b3-1649068904762)]

1.序列化的中序遍历方式得到全部的子序列

[图片上传失败...(image-8fec11-1649068904762)]

2.全部子序列的不重复的集合

使用set集合

[图片上传失败...(image-f37a50-1649068904762)]

3.全排列的子序列

[图片上传失败...(image-e0acf9-1649068904762)]

[图片上传失败...(image-4f12-1649068904761)]

在依次回退的时候递归需要保证原来的顺序,为了正确执行

4.分支限界法去重全排列集合

通俗来讲为剪枝

[图片上传失败...(image-766a6d-1649068904761)]

题目练习

1.尝试字符与数字对应

[图片上传失败...(image-a9ebf5-1649068904761)]

1.1. 爬楼梯

\70. Climbing Stairs (Easy)

Leetcode (opens new window)/ 力扣(opens new window)

题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。

定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。

第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。

[图片上传失败...(image-c66cad-1649068904761)]

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

方法1:利用状态方程:

<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" cid="n38" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: var(--codeblockbg-color); position: relative !important; border-radius: 3px; color: var(--codeblockfont-color); padding: 0px 4px; overflow-wrap: break-word; line-height: 1.6em; width: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;" lang="java">class Solution{
public int climbStairs(int n){
int []dp = new int[n+1];
dp[0] = 1,dp[1] = 1;
for(int i = 0;i<n+1;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}</pre>

技巧二:滚动数组(优化dp空间)O(n)~O(1)

<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" cid="n41" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: var(--codeblockbg-color); position: relative !important; border-radius: 3px; color: var(--codeblockfont-color); padding: 0px 4px; overflow-wrap: break-word; line-height: 1.6em; width: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;" lang="java">class Solution{
public int climbStairs(int n){
int p = 0, q =0 r = 1;
for(int i = 0; i< n+1;i++){
p = q;
q = r;
r = p + q;
}return r;
}
}</pre>

补充:

技巧:矩阵快速幂复杂度n小的时候可以

通项公式

2.打家劫舍198(非环状的房屋)

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：

输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。示例 3：

输入：nums = [0] 输出：0

由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以

[图片上传失败...(image-20ea44-1649068904760)]

<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" cid="n56" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: var(--codeblockbg-color); position: relative !important; border-radius: 3px; color: var(--codeblockfont-color); padding: 0px 4px; overflow-wrap: break-word; line-height: 1.6em; width: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;" lang="java">public int rob(int[] nums) {
int pre2 = 0, pre1 = 0;
for (int i = 0; i < nums.length; i++) {
int cur = Math.max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}</pre>

2.1213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" cid="n62" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: var(--codeblockbg-color); position: relative !important; border-radius: 3px; color: var(--codeblockfont-color); padding: 0px 4px; overflow-wrap: break-word; line-height: 1.6em; width: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;" lang="">输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。</pre>

示例 2：

<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" cid="n64" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: var(--codeblockbg-color); position: relative !important; border-radius: 3px; color: var(--codeblockfont-color); padding: 0px 4px; overflow-wrap: break-word; line-height: 1.6em; width: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;" lang="">输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。</pre>

示例 3：

矩阵问题:

动态规划

我们用 f(i, j)f(i,j) 表示从左上角走到 (i, j)(i,j) 的路径数量，其中 ii 和 jj 的范围分别是 [0, m)[0,m) 和 [0, n)[0,n)。

由于我们每一步只能从向下或者向右移动一步，因此要想走到 (i, j)(i,j)，如果向下走一步，那么会从 (i-1, j)(i−1,j) 走过来；如果向右走一步，那么会从 (i, j-1)(i,j−1) 走过来。因此我们可以写出动态规划转移方程：

f(i, j) = f(i-1, j) + f(i, j-1) f(i,j)=f(i−1,j)+f(i,j−1)

需要注意的是，如果 i=0i=0，那么 f(i-1,j)f(i−1,j) 并不是一个满足要求的状态，我们需要忽略这一项；同理，如果 j=0j=0，那么 f(i,j-1)f(i,j−1) 并不是一个满足要求的状态，我们需要忽略这一项。

初始条件为 f(0,0)=1f(0,0)=1，即从左上角走到左上角有一种方法。

最终的答案即为 f(m-1,n-1)f(m−1,n−1)。

细节

为了方便代码编写，我们可以将所有的 f(0, j)f(0,j) 以及 f(i, 0)f(i,0) 都设置为边界条件，它们的值均为 11。

<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" cid="n78" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: var(--codeblockbg-color); position: relative !important; border-radius: 3px; color: var(--codeblockfont-color); padding: 0px 4px; overflow-wrap: break-word; line-height: 1.6em; width: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;" lang="java">class Solution {
public int uniquePaths(int m, int n) {
int[][] f = new int[m][n];
for (int i = 0; i < m; ++i) {
f[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
f[0][j] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
}
复杂度分析</pre>

时间复杂度：O(mn)O(mn)。

空间复杂度：O(mn)O(mn)，即为存储所有状态需要的空间。注意到 f(i, j)f(i,j) 仅与第 ii 行和第 i-1i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 mm 和 nn 使得 m \leq nm≤n，这样空间复杂度降低至 O(\min(m, n))O(min(m,n))。

DP(动态规划）