先介绍了动态规划的概念，使用的必要条件，和其他类似算法的区别和联系。然后是实战，coding部分。
概念
Dynamic programming (DP) is as hard as it is counterintuitive.
dp 不太好想出来，所以是 counterintuitive，但如果想出来，那么程序时间效率上会很高。
定义：
Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once.
使用dp 的两个必要条件：
- 最优子结构
最优子结构，如果简单理解，那么可以等同于递归。如果一个问题能够使用递归解决，那么就具有最优子结构。
Optimal substructure simply means that you can find the optimal solution to a problem by considering the optimal solution to its subproblems.
对于一个子问题的最优解，那么也是原来问题的最优解。
举例说明一个不是最优子结构的问题. according to wikipedida:
“Using online flight search, we will frequently find that the cheapest flight from airport A to airport B involves a single connection through airport C, but the cheapest flight from airport A to airport C involves a connection through some other airport D.”
- 重复的子问题
正因为有了 overlapping subproblems，那么才是需要 memory，才是需要cache。使用 Fibonacci problem 举例说明：
如上图所示，计算 fib(4) 和计算 fib(3) 都是需要计算fib(1) 和fib(2)。 那么这个时候就是有重复的子问题。
时间复杂度分析
In programming, Dynamic Programming is a powerful technique that allows one to solve different types of problems in time $O(n^2)$ or $O(n^3)$ for which a naive approach would take exponential time.
使用 $O(n^2) $或者 $O(n^3)$的时间复杂度从而避免指数级运算。所以有下面的额表示方式：
One can think of dynamic programming as a table-filling algorithm: you know the calculations you have to do, so you pick the best order to do them in and ignore the ones you don’t have to fill in.
Tabulation is an approach where you solve a dynamic programming problem by first filling up a table, and then compute the solution to the original problem based on the results in this table.
表格实现了memory机制，优化了时间效率。memory 就等同于 cache，这个基本假设是有多次相同的问题需要被解决，如果没有重复的问题，那么也是没有必要使用memory 进行时间上的优化的。
两种不同的思考方式：
-
Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.
-
Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.
第一种类似带有memory机制的递归。memory机制就是一种典型的空间换取时间的方式。
dp 和其他算法的不同
- Divide and conquer is slightly a different technique. In that, we divide the problem in to non-overlapping subproblems and solve them independently, like in merge sort and quick sort.
- Greedy Algorithms which make a decision once and for all every time they need to make a choice, in such a way that it leads to a near-optimal solution.
- Dynamic programming is basically, recursion plus using memory. The intuition behind dynamic programming is that we trade space for time.
大多数dp 问题都可以归结为这两类：
- Optimization problems.
- Combinatorial problems.
The optimization problems expect you to select a feasible solution, so that the value of the required function is minimized or maximized. Combinatorial problems expect you to figure out the number of ways to do something, or the probability of some event happening.
最优解得到是最大值或者最小值；组合问题得到是解的个数。
实例
解题步骤
-
Define subproblems
-
Write down the recurrence that relates subproblems
-
Recognize and solve the base cases
-
对问题的定义（一般是一维、二维表格）
-
找到当前问题和子问题的转换关系
-
初始化
1-dimensional DP Example
问题一：
Problem: given n, find the number of different ways to write n as the sum of 1, 3, 4
Example: for n = 5, the answer is 6
1
2
3
4
5
6
7
|
5
= 1+1+1+1+1
= 1+1+3
= 1+3+1
= 3+1+1
= 1+4
= 4+1
|
解题步骤
- 对问题的定义
Let $D_n$ be the number of ways to write the sum of 1, 3, 4
- 转换关系
$D_n = D_{n−1} + D_{n−3} + D_{n−4}$
- 初始化
$D_0 =D_1 =D_2 =1$, and $D_3 =2$
c++ 代码实现
版本一：就是一种dfs 的思路
1
2
3
4
5
6
7
8
|
int dfs(int n)
{
// 这个说是dp 但是更像是dfs，只不过
if (n ==0 || n ==1 ||n ==2) return 1;
if(n ==3) return 2;
return dfs(n-1) +dfs(n-3)+dfs(n-4);
}
|
空间复杂度是 $O(n)$，时间是 $O(n)$， 空间换取时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
unordered_map<int, int> cache;
int dfs(int n)
{
// 这个说是dp 但是更像是dfs，只不过
if (n ==0 || n ==1 ||n ==2) return 1;
if(n ==3) return 2;
if (cache.count(n)) return cache[n];
else
{
cache[n] =dfs(n-1) +dfs(n-3)+dfs(n-4);
return cache[n];
}
}
|
python 实现，时间复杂度 $O(n)$ 空间复杂度 $O(n)$
1
2
3
4
5
6
7
8
9
10
11
|
cache ={}
def dp(n):
if n==0 or n ==1 or n==2: return 1
if n ==3: return 2
if n in cache: return cache[n]
else:
cache[n] =dp(n-1) +dp(n-3) +dp(n -4)
return cache[n]
print(dp(5))
|
问题二： Tri Tiling （这里是需要补充的）
Given n, find the number of ways to fill a 3×n board with dominoes
c++ 代码，关键是动态转移方程。
$$
\begin{split}
A_n &= A_{n-2} +B_{n-1} + C_{n-1} \\
B_n &= A_{n-1} + B_{n-2}
\end{split}
$$
讲解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int fun(int n , vector<int> & a, vector<int>& b)
{
a[0] =1, a[1] =0;
b[0] =1, b[1] =1;
for(int i =2; i<=n; i++)
{
a[i] =a[i-2] +2*b[i-1];
b[i] =a[i-1] +b[i-2];
}
return a[n];
}
int main()
{
int n;
cin >>n;
vector<int> a1(n+1), b1(n+1);
cout << fun(n, a1, b1)<< endl;
return 0;
}
|
还有一个比较简单的题目，
Given n, find the number of ways to fill a 2*n board with dominoes
动态转移方程（这个相对上一个考虑的情况少一些）
$$
\begin{split}
A_n &= n if n ==1 || n ==2 \\
A_n &= A_{n-1} + A_{n -2} else\\
\end{split}
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int fun(int n , vector<int> & a)
{
a[1] =1, a[2] =2;
for(int i =3 ; i<=n; i++)
a[i] =a[i-1] + a[i-2];
return a[n];
}
int main()
{
int n;
cin >>n;
vector<int> a(n+1);
cout << fun(n, a)<< endl;
return 0;
}
|
2-dimensional DP Example
问题一：最长子序列
Problem: given two strings x and y, find the longest common subsequence (LCS) and print its length
解题步骤：
- 对问题的定义
$D_{ij}$ 表示 $x_{1, …, i}$ 和$y_{1, …, j}$ 的LCS 的长度
- 转换关系（回文串就是前后缀问题）
- $D_{ij} =D_{i-1, j-1} +1$ if $x_i =y_j$， 因为both of them contribute to the LCS
- $D_{ij} =max{D_{i-1, j}, D_{i, j-1}} $ 否则的话
- 初始化(就是解决最小的问题，就是当 $i-1 ==0$ 的时候， 或者bad case 是如何进行处理)
$D_{i0} =D_{0j} =0$
c++ 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<iostream>
using namespace std;
const int MAXV =10;
int n,m;
int lcs(char * str1, char * str2)
{
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i =1; i<= n; i++)
for(int j =1; j<=m; j++)
{
if(str1[i] ==str2[j])
dp[i][j] =dp[i-1][j-1] +1;
else
dp[i][j] =max(dp[i][j-1], dp[i-1][j]);
}
return dp[n][m];
}
int main()
{
char s1[MAXV], s2[MAXV];
cin >>n>>m;
cin >>s1+1>> s2+1;
cout << lcs(s1, s2)<< endl;
return 0;
}
|
python实现。在申请空间的时候，多申请一圈的空间。并且在判断的时候，使用 str1[i-1] ==str2[j-1] 来处理越界的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
# 边界条件是根据实际意义出发
str1 ="abcd"
str2 ="bad"
def lcs(str1, str2):
n, m =len(str1), len(str2)
dp =[ [0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m +1):
if(str1[i-1] ==str2[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[n][m]
print(lcs(str1, str2))
|
How can we now find the sequence? To find the sequence, we just walk backwards through matrix starting the lower-right corner. If either the cell directly above or directly to the right contains a value equal to the value in the current cell, then move to that cell (if both to, then chose either one). If both such cells have values strictly less than the value in the current cell, then move diagonally up-left (this corresponts to applying Case 2), and output the associated character. This will output the characters in the LCS in reverse order. For instance, running on the matrix above, this outputs DABA.
上面的是从底到上思路（迭代）
然后看第二种思路（从上到下），那么就递归+ memory
1
2
3
4
5
6
7
8
|
LCS(S,n,T,m)
{
if (n==0 || m==0) return 0;
if (arr[n][m] != unknown) return arr[n][m]; // <- added this line (*) if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1);
else result = max( LCS(S,n-1,T,m), LCS(S,n,T,m-1) );
arr[n][m] = result;
return result;
}
|
扩展题目
More about LCS: Discussion and Extensions. An equivalent problem to LCS is the “mini- mum edit distance” problem, where the legal operations are insert and delete.
转移方程
$$ dp[i][j] = \begin{cases}
1 +min{dp[i][j-1], dp[i-1][j], dp[i-1][j-1]} +1& x_i \neq x_j \\
dp[i-1][j-1]& x_i = x_j
\end{cases}$$
c++ 实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int minDistance(string word1, string word2) {
int n =word1.size(), m =word2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
// 初始化
for(int i =0; i<=m ; i++) dp[i][0] =i;
for(int i =0; i<=n ; i++) dp[0][i] =i;
for(int i =1; i<=n ; i++)
for(int j =1; j<=m; j++ )
{
if(str1[i-1] ==str2[j-1])
dp[i][j] =dp[i-1][j-1] ;
else
dp[i][j] =min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) +1;
}
return dp[n][m];
}
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def edit_distance(str1, str2):
n, m =len(str1), len(str2)
dp =[ [0] *(m+1) for _ in range(n+1)]
# 初始化
for i in range(n+1): dp[i][0] =i
for i in range(m +1): dp[0][i] =i
for i in range(1, n+1):
for j in range(1, m+1):
if str1[i-1] ==str2[j-1]:
dp[i][j] =dp[i-1][j-1]
else:
dp[i][j] =min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) +1
return dp[n][m]
str1 ="horse"
str2 ="ros"
print(edit_distance(str1, str2))
|
Interval DP (间隔或区间dp)
Problem: given a string $x = x_{1…n} $, find the minimum number of characters that need to be inserted to make it a palindrome
解题思路
- 问题的定义
Let $D_{ij}$ be the minimum number of characters that need to be inserted to make $x_{i…j}$ into a palindrome
- 转换关系
$$ dp[i][j] = \begin{cases}
1 + min(dp[i+1][j], dp[i][j-1]) & x_i \neq x_j \\
dp[i+1][j-1]& x_i \eq x_j
\end{cases}
$$
- 初始化
Find and solve the base cases: $D_{ii} = D_i, i−1 = 0 $ for all $ i$
The entries of D must be filled in increasing order of $j − i$
An alternate solution
- Reverse $x $to get $x^R$
- The answer is $n−L $, where $ L $is the length of the LCS of $ x$ and $x^R$
填充表格的过程是按照主对角线进行填充的，最后填充的点是 dp[0][n-1]。第一层循环是一个gap 的循环，是按照主对角线进行遍历的。\\ 这样遍历，非常nice 的代码。
代码实现部分（按照道理是只需要初始化主对角线就行，但是下面的代码把所有的值初始化为0）
c++ 代码实现部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
int n ;
string str1;
cin >>n;
cin >> str1;
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int gap =1; gap<n; gap++)
// 这个是一种全新的遍历方式
for(int i =0, j =gap +i; j<n; i++, j++)
{
if(str1[i] ==str1[j])
dp[i][j]= dp[i+1][j-1];
else
dp[i][j] =min(dp[i+1][j], dp[i][j-1] ) +1;
}
cout << dp[0][n-1]<< endl;
return 0;
}
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def dp(str1):
n =len(str1)
# 初始化
dp =[[0]*n for _ in range(n)]
for gap in range(1, n):
i =0
j =i +gap
while j<n:
dp[i][j] = dp[i+1][j-1] if str1[i] ==str1[j] else min(dp[i+1][j], dp[i][j-1]) +1
i += 1
j += 1
return dp[0][n-1]
str1 ="abcd"
print(dp(str1))
|
The Knapsack Problem 背包问题也是可以纳入到 dp系列中
In the knapsack problem we are given a set of n items, where each item i is specified by a size si and a value vi. We are also given a size bound S (the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).
matrix product parenthesization problem.
参考文献
standford Dynamic Programming
dp-cmu 课件
Demystifying Dynamic Programming
The Ultimate Guide to Dynamic Programming
Dynamic programming [step-by-step example]
Introduction to Dynamic Programming 1
Tutorial For Dynamic Programming
之前的
动态规划的求解需要考虑三个问题：
- 状态怎么表示
- 怎么计算每个状态
- 怎么初始化
** Unique Paths II**
原题连接
对于动态规划，需要考虑三个问题：
- 状态怎么表示： f[i][j] 表示是(i, j) 这点的方案数
- 怎么计算下一步： f[i][j] 只有两个来源，一种是从上面走下来，一种是从左边走下来
- 怎么初始化：
dp很重要的一点： 使用到的状态之前都已经计算过。针对这道题目，求解方案数，有可能最后的结果超过了int 的范围，所以使用long long应该是比较好的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
public:
// f[i][j] 表示(i, j) 这个点路径的个数
// 转移 f[i][j] =f[i-1][j] or f[i][j-1] 这样的方式
// 初始化, 0 if nums[i][j] ==1 , else 1
int uniquePathsWithObstacles(vector<vector<int>>& nums) {
if(!nums.size() || !nums[0].size()) return 0;
int n =nums.size(), m =nums[0].size();
if (nums[0][0]) return 0;
vector<vector<long long>> f(n, vector<long long>(m)); // 默认初始为0， 因为这个是在 public 中
f[0][0] =1;// 这个是从左上角开始的, 因为上文已经判断case，所以可以直接进行初始化
for(int i =0; i< n; i++)
{
for(int j =0; j<m; j++)
{
if(i || j) f[i][j] =0;// 只有在 非
if(!nums[i][j])
{
if(i) f[i][j] += f[i-1][j] ;
if(j) f[i][j] += f[i][j-1];
}
}
}
return f[n-1][m-1];
}
};
|
triangle
LeetCode 版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
// 实现的时候，如何进行遍历是，我的弱点。
// 这种三角形在(i, j) 上是有特点的，因为类似一种直角三角形
int minimumTotal(vector<vector<int>>& triangle) {
int n =triangle.size();
// 滚动数组
vector<int> f(triangle[n-1].begin(), triangle[n-1].end()), g(n);// f()是拷贝， g是初始化
// cpp 语法，这里是没有 triangle[-1] 表示的，不是python 中的
for(int i =n-2; i>=0; i--)
{
for(int j =0; j<=i; j++) // 直角三角形的特点
{
g[j] =min(f[j], f[j+1]) +triangle[i][j];
}
f =g;
}
return f[0];
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin >>n;
vector<vector<int>> arr(n, vector<int>(n));
for(int i =0;i<n; i++)
for(int j =0; j<=i; j++) cin>> arr[i][j];
vector<int> f(arr[n-1].begin(), arr[n-1].end()), g(n);// 如何去理解 g(n) 作为一种备胎，滚动数组
for(int i =n-2; i>=0; i--)
{
for(int j =0; j<=i; j++)
{
g[j] =min(f[j], f[j+1])+ arr[i][j]; // 这步骤很重要
}
f =g;
}
cout<< f[0] <<endl;
return 0;
}
|
354. Russian Doll Envelopes
原题链接
一共有两种解法。先进行排序，然后转换成最长连续递增子序列,。时间复杂度分析： 排序最快是 $nlogn$， 如果使用dp，那么总的是$n^2$; 如果使用二分总的是$nlogn$。下面是第一种解法，使用dp 的思想。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n =envelopes.size();
vector<int> dp(n,0);
dp[0] =1;
int result =1;
sort(envelopes.begin(), envelopes.end());
for(int i =0; i<n; i++)
{
for(int j =0;j<i ;j++)// 遍历前面所有的状态的
{
if(envelopes[i][0]> envelopes[j][0] && envelopes[i][1]> envelopes[j][1] )
dp[i] =max(dp[i], dp[j]+1);
}
result =max(result, dp[i]);
}
return result;
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// sort 然后最长递增子序列吧
// dp[i] 表示长度为i 的最长递增, 转移方程 dp[i] =max(dp[i], dp[j]+1) j<i, 初始化 dp[0] =0
int maxEnvelopes(vector<vector<int>>& arr)
{
if(arr.empty()) return 0;
int result =1;
int n =arr.size();
vector<int> dp(n);
sort(arr.begin(), arr.end());// 默认按照第一个元素进行递增排序
for(int i =0; i<n ;i++)
{
for(int j=0; j<i; j++)
{
dp[i] =max(dp[i], dp[j] +1);
}
result =max(result, dp[i]);
}
return result;
}
int main()
{
int n ;
cin >>n;
vector<vector<int>> arr(n, vector<int>(2));
for(int i =0; i<n;i++)
{
for(int j =0; j<2;j++)
cin >>arr[i][j];
}
cout << maxEnvelopes(arr) <<endl;
return 0;
}
|
第二种解法，使用二分的思想进行检索，总的时间复杂度能够达到 $O(nlog n)$.使用python 实现。
leetcode 版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution(object):
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if not envelopes: return 0;
envelopes.sort(key =lambda x:(x[0], -x[1]))
# 按照第一个元素升序，然后第二个元素降序
# 二分查找 第二个元素的位置，当第一个元素相同的时候
#print(envelopes)
lst =[]
for fir, sec in envelopes:
y =sec
if lst ==[] or y> lst[-1]:
lst.append(y)
else:
# 二分查找y 合适的位置
left, right =0, len(lst)
while left<right:
mid =(left +right)//2
if y<= lst[mid]:
right =mid
else:
left =mid +1
lst[left] =y
return len(lst)
|
单机版本
(c++ 中在main 或者 普通function 中对vector 申请空间之后，都是有默认的初始化的。比如对于 vector ，那么都是初始化成0)
python 中sort() 函数中的自定义sort 是非常nice 的一定写法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
# 先排序，然后就是 最长递增子序列的问题, 而该问题使用二分查找进行解决
def maxEnvelopes(arr):
if not arr: return 0
arr.sort(key =lambda x: (x[0], -x[1]))
lst =[]
#print(arr)
for _, b in arr:
import ipdb
#ipdb.set_trace()
y =b
if lst==[] or y> lst[-1]:
lst.append(y)
else:
# 二分查找
left, right =0, len(lst)-1
while left <right:
mid =(left+ right)//2
if( y< lst[mid]):
right =mid
else:
left =mid+1
lst[left] =y
return len(lst)
if __name__ =="__main__":
n =int(input())
arr =[[0]*2] *n
for i in range(n):
arr[i] =input().split(" ")
arr[i] =[int(a) for a in arr[i]]
print(arr)
print(maxEnvelopes(arr))
|
338. Counting Bits
原题
思想： 二进制的思想。使用dp 的时候，往往初始化 f[0] 然后在遍历循环的时候，就从i =1 的时候进行循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
vector<int> countBits(int num) {
vector<int> f(num+1);
f[0] =0;
for(int i =1; i<=num; i++)
{
f[i] =f[i/2] + i&1; // 表示i 的个位是不是1
}
return f;
}
};
|
单机版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>> n;
vector<int> f(n+1);
f[0] =0;
for(int i =1; i<=n; i++)
{
f[i] =f[i >>1] + i&1;// 可以写得更加简单一点
}
for(auto u : f)
cout << u<< " ";
cout<<endl;
return 0;
}
|
329. Longest Increasing Path in a Matrix
原题
leetcode 版本
本题的特点，没有一个非常明确的转移顺序（枚举顺序）。因为是可以有四个方向进行选择的，这个枚举顺序是不好写的。所以可以学习以下下面的代码。写的比较nice。
这个题目很容易使用f[i][j] 表示点 (i,j) 位置的最长的路径，但是怎么转移？ 这个是没有固定的说是按照行枚举还是按照列进行枚举的。所以这个转移方程是不太好些的，所以这里用到一种方法，叫做记忆化搜索.
这种使用 dx, dy 的方式，然后得到新的坐标(a, b)。这种方式是比较通用的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public:
int n, m;
vector<vector<int>> f, g;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
if (f[x][y] != -1) return f[x][y];
f[x][y] = 1;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] < g[x][y])
f[x][y] = max(f[x][y], dp(a, b) + 1);
}
return f[x][y];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.empty()) return 0;
g = matrix;
n = g.size(), m = g[0].size();
f = vector<vector<int>>(n, vector<int>(m, -1));
int res = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
res = max(res, dp(i, j));
return res;
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<iostream>
#include<vector>
using namespace std;
int n, m;
vector<vector<int>> f, arr;
int dx[4] ={-1, 0, 1, 0}, dy[4] ={0, 1, 0, -1};
int dp(int i, int j)
{
if(f[i][j] != -1) return f[i][j];
f[i][j] =1;
for(int k =0; k<4 ;k++)
{
int a = i+dx[k], b =j+dy[k];
if(a >=0 && a< n && b>= 0 && b<m && arr[a][b] > arr[i][j])
f[i][j] =max(f[i][j], dp(a, b)+1);
}
return f[i][j];
}
int main()
{
cin>> n>>m;
arr =vector<vector<int>>(n, vector<int>(m));
for(int i =0; i<n; i++)
for(int j =0; j<m ;j++)
cin >> arr[i][j];
// 初始化
f =vector<vector<int>>(n, vector<int>(m, -1));
int res =0;
for(int i =0; i<n; i++)
for(int j =0; j<m; j++)
{
res =max(res, dp(i, j));
}
cout<< res<<endl;
return 0;
}
|
Coin change
原题链接
使用硬币组成给定的钱数，硬币可以无限使用，钱的总数是一定的，要求尽可能使用少的硬币。
是一种完全背包问题，从小到大进行枚举。(多重背包问题是对于完全背包问题的一种约束，后者是物品可以无限的选，前者是对于物品的数量有限制。也就是说多重背包中，某件物品只能选择几个)
f[i] 表示钱数是i 需要使用最少的硬币数量。 f[i] =min(f[i], f[i-c]+1) 分成选和不选两种方案。初始化 f[0] =0 （根据实际问题含义进行初始化）。背包问题是就是先枚举物品，然后再枚举体积（这里 是金钱）的做法。
LeetCode版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> f(amount+1, INT_MAX/2);
f[0] =0;
for(auto c : coins)
for(int i =c ; i<= amount; i++)
{
f[i] =min(f[i], f[i-c]+1);
}
if(f[amount] == INT_MAX/2) return -1;
else return f[amount];
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> coins(n);
int amount ;
cin >>amount;
vector<int> f(amount+1, INT_MAX/2); // 这个在cpp 中的常数还是经常使用的哦
f[0] =0;
for(int i =0; i<n ; i++)
{
int c;
cin >>c;
for(int j =c; j<= amount; j++)
f[j] =min(f[j], f[j-c]+1);
}
if(f[amount] ==INT_MAX/2) cout << -1 <<endl;
else cout << f[amount] <<endl;
return 0;
}
|
- Maximal Square
题目： 最大的包含全部都是1 的正方形。
f[i][j] 表示右下角位置是 (i, j) 的正方形的边长。这个转移和上面increasing path 是一样的，都是没有固定的枚举方式，所以使用 dx dy 得到下一个新的坐标。根据上方，左边和左上角进行求解最小的边长。
原题链接
LeetCode版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
// 如何表示，dp[i][j] 表示以位置(i,j)为右下角的正方形的全部都是1的面积。
// 如何计算 dp[i][j] =min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 这个是转移方程
// 初始化, dp ={0}
int maximalSquare(vector<vector<char>>& matrix) {
if(!matrix.size() || !matrix[0].size()) return 0;
int n =matrix.size(), m =matrix[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
int res =0;
for(int i =0; i<n; i++)
{
for(int j =0; j<m; j++)
{
//if (!i || !j) dp[i][j] =0;
if(matrix[i][j] =='0') dp[i][j] =0;
else
{
dp[i][j] =1;
if(i >=1 && j>=1)
{
// 那么这个就十分的通顺，计算的就是最小的边长
dp[i][j] += min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) ;
}
res =max(res, dp[i][j]);
}
}
}
return res*res;// dp 得到的是边长，不是面积
}
};
|
单机版中array 的输入是 int 类型，所以在进行 array[i][j] ==‘1’ 判断就是错误的， 因为 int 类型的 1 和 char 类型的 ‘1’ 这个是不一样的。
所以在 c++ 或者 c 中一定要注意这个小的区别。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m;
vector<vector<int>> arr, dp;
int main()
{
cin>>n>>m;
// 需要申请空间的，即使是没有初始化成特定的值
/*
arr =vector<vector<int>>(n, vector<int>(m));
for(int i =0; i<n; i++)
for(int j =0; j<m; j++)
cin>>arr[i][j];
*/
arr ={{1, 0 , 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1,1}, {1, 0, 0, 1, 0}};
// 这种先是定义，然后再申请空间，也是昌吉nice的e
dp =vector<vector<int>>(n, vector<int>(m, 0));
int res =0;
for(int i =0;i<n; i++)
for(int j =0; j<m; j++)
{
if(arr[i][j] =='0') dp[i][j] =0;
else
{
dp[i][j] =1; // 这个条件很重要，因为当 arr[i][j] ==1 的时候，该位置就组成了dp[][] ==1
if(i>=1 && j>=1) dp[i][j] += min(dp[i-1][j-1], min(dp[i][j-1],dp[i-1][j]) );
res =max(res, dp[i][j]);
}
}
cout<< res*res <<endl;
return 0;
}
|
Out of boundary paths(到这里了)
leetcode 版本
原题
f[i][j][k] 表示位置在(i, j) 并且还剩下k 步，走出边界的方案数。同样使用到了记忆化搜索，当计算过的时候，直接返回结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution {
public:
// 这个应该是最为复杂的dp 了吧。dp[i][j][k] 表示 (i,j) 同时还有k 步的时候，走出边界的方案数
vector<vector<vector<int>>> f;
int dx[4] ={-1, 0, 1, 0}, dy[4] ={0, 1, 0, -1};
int mod =1000000007
int findPaths(int m, int n, int N, int i, int j) {
f =vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(N+1, -1)));
return dp(m, n, N, i, j);
}
int dp(int m, int n, int k, int x, int y)
{
int &v =f[x][y][k];
if(v !=-1) return v;
v =0;
if(!k) return v;
for(int i =0; i<4; i++)
{
int a =x +dx[i], b = y+dy[i];
if(a <0 || a ==m || b<0 || b ==n) v++;
else v += dp(m, n, k -1, a, b);
v %= mod;
}
return v;
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<iostream>
#include<vector>
using namespace std;
// dp[i][j][k] 表示(i, j) 位置同时还剩下k 步，走出边界的方案书
// 转移 dp[i][j][k] +=1 if 走出了边界 else += dp[a][b][k-1]
// dp[i][j][k] =0
vector<vector<vector<int>>> f;
int MOD =1000000007;
int dx[4] ={-1, 0, 1, 0}, dy[4] ={0, 1, 0, -1};
int dp(int m, int n, int k, int x, int y)
{
int &v =f[x][y][k]; // 记忆化搜索
if (v !=-1) return v;
v =0;
if (!k ) return v;
// 枚举四个方向
for(int i =0; i<4; i++)
{
int a =x+dx[i], b =y+dy[i];
if(a <0 || a==m || b<0 || b ==n ) v ++;
else v +=dp(m,n, k-1, a, b);
v %=MOD;
}
return v;
}
int main()
{
int m, n, N, i,j;
// 简单的先通过case 再说
m=1, n =3, N =3, i =0, j=1;
// 这个最后为什么手机 N+1, 测试一下边界
f= vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(N+1, -1)));
cout<< dp(m, n, N, i, j)<< endl;
return 0;
}
|
Decode Ways
存在一个英文字母到数字的映射表，给定数字，问有几种 decode 方式。
f[i] 表示前 i个数字一共的解码方式。可以分为两种情况，一种方案是当前的数字可以映射到一个字母，另一种方案是当前数字和上一个数字映射到一个字母。
f[i] += f[i-1] （这种关系表示一种累加，继承的意思）。
（为什么分成了两种情况，映射表中是1 到26，数字使用两位就可以直接表示）
网站链接
LeetCode 版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
public:
// dp 的思路， dp[i] 表示前i 个字符串的总的方案书
// 转移 dp[i] += dp[i-1] if s[i-1] !='0' , += dp[i-2] if 10<= int(s[i-2: i-1]) <=26
// dp 一定是要进行初始化的
// 卧槽关于数据类型，这个是第二遍了吧， 0 和 '0' 不是一个数据类型
int numDecodings(string s) {
int n =s.size();
vector<int> f(n+1);
s =' '+s;
f[0] =1;
for(int i =1; i<=n ;i++)
{
f[i]=0;
if(s[i] !='0') f[i] +=f[i-1];
if(i >1)
{
int t =(s[i-1] -'0')*10 +s[i] -'0';
if (t >=10 && t<= 26) f[i] += f[i-2];
}
}
//for(auto u : f) cout<< u<< " ";
return f[n];
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include<iostream>
#include<vector>
#include<string>
using namespace std;
/**
首先是
f[i] 表示前 i 个可以解码的总数
转移方程 f[i] += f[i-1] if s[i-1] !='0'
f[i] += f[i-2] if 10<=int(s[i-2,i])<=26
初始化 f[i] =0 && f[0] =1
**/
int main()
{
string s;
cin>> s;
int n =s.size();
vector<int> f(n+1);
// 边界问题
s = ' '+s;
f[0] =1;
for(int i =1 ; i<=n; i++)
{
f[i] =0;
if(s[i] !='0') f[i] += f[i-1];
if(i>1)
{
int t =(s[i-1]-'0')*10 + s[i] -'0';
if( t<=26 && t>= 10) f[i] += f[i-2];
}
}
cout<< f[n]<<endl;
return 0;
}
|
** ugly number**
leetcode 版本
原题链接
vector.back() 访问返回最后一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
// 使用三个指针，之前使用python 使用过类似的算法才对
int nthUglyNumber(int n) {
vector<int> q;
q.push_back(1);
int i =0, j=0,k =0;
while( --n)
{
int t =min(q[i]*2, min(q[j]*3, q[k]*5));
q.push_back(t);
// 这个是并列的if
if( t == q[i]*2) i++;
if(t ==q[j] *3) j++;
if(t == q[k] *5) k++;
}
return q.back();
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >>n;
//vector<int> arr(n+1);
vector<int> q;
//for(int i =0; i<n; i++) cin >>arr[i];
q.push_back(1);
int i =0,j =0, k =0;
while( --n)
{
int t =min(q[i] *2, min(q[j]*3, q[k]*5));
q.push_back(t);
if(q[i]*2 == t) i++;
if(q[j] *3 ==t) j++;
if(q[k] *5 ==t) k++;
}
cout<< q.back()<<endl;
// vector.back() 是访问最后一个数字
// vector.front() 是访问第一个数字
return 0;
}
|
** Distinct Subsequences**
LeetCode 版本
链接
思路： 使用dp。
含义：f[i][j] 表示source 为i ，dest 为j 的情况下，最大的方案数
转换： f[i][ j] = f[i-1][j] 不管什么情况下，对于source 中的i 都可以不选
f[i][j] 对于 s[i] ==d[j] 的情况下， f[i][j] += f[i-1][j-1] ， 当两个相同的时候，这个是可以选择的。
（不选就没有累加的方案数，选择就是累加的方案数）
子序列和子串是不同的概念， 子序列要求的不连续的index，子串要求的是连续的index。最后求的是s 能够拼凑成 t的方案数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
// f[i][j] = f[i-1][j] 或者 =f[i-1][j-1] if(s[i] ==t[j])
long long numDistinct(string s, string t) {
int m =s.size(), n =t.size();
vector<vector<long long>> f(m+1, vector<long long>(n+1));
// 初始化
for(int i =0; i<=m; i++) f[i][0] =1;
for(int i =1; i<=m; i++)
for(int j =1; j<=n ; j++)
{
f[i][j] = f[i-1][j];
if(s[i-1] ==t[j-1]) f[i][j]+= f[i-1][j-1];// 这个累加的是不选的方案，然后如果相同，那么就再累加一下。
}
return f[m][n];
}
};
|
单机版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
string S;
string T;
cin>> S;
cin>> T;
int n =S.size(), m =T.size();
vector<vector<long long>> f(n+1, vector<long long>(m+1));
for(int i =0;i<n; i++) f[i][0] =1;
for(int i =1; i<=n; i++)
for(int j =1; j<=m ; j++)
{
f[i][j] = f[i-1][j];
if(S[i-1] == T[j-1]) f[i][j] += f[i-1][j-1];
}
cout<< f[n][m] <<endl;
return 0;
}
|
- Palindrome Partitioning II
原题链接
这道题使用两次 dp。
第一次： dp[i:j]方便的判断任意两个区间组成的字符串是否是回文数。
第二次： dp[i] 前i 个字符串中最少有多少个回文数(题目要求是最少的 partition的数量)
两个for 循环，保证了每次枚举的是 i( 1-n) 的left and right，二部仅仅是 1-n 的left and right。
对于dp 的debug，一般先从逻辑上（看代码）进行找错；实在不行才是每行输出。因为dp 当数据量比较大的时候，这个是不容易输出的。
- leetCode-132 95:17 讲解连接 https://www.bilibili.com/video/av35161871/?p=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
public:
// f[i] 表示前i 个字母是多少个回文串， 数量的回文串 -1 就是 需要多少 刀
// 分成多少个 palindrome partitioning，
// 使用动规 进行初始化，然后
int minCut(string s) {
int n =s.size();
vector<vector<bool>> c(n, vector<bool>(n, false)); // 这个c 表示从 [j][i] 这个子串是不是回文串, 这个操作很神奇
for(int i =1;i<=n ; i++)
for(int j =0; j+i-1 <n; j++)
{
int l =j, r =j+i-1;
c[l][r] = s[l] ==s[r] && (l+1 > r-1 || c[l+1][r-1] );
}
for(auto u : c)
{
for(auto v : u) cout << v<< " ";
cout <<endl;
}
vector<int> f(n+1);
f[0] =0;
for(int i =1; i<=n ;i++)
{
f[i] =INT_MAX;
for(int j =1; j<=i; j++)
if(c[j-1][i-1]) // 为甚这个是回文串，之后，然后才能+1
f[i] =min(f[i], f[j-1]+1);
}
return f[n]-1;
}
};
|
这个是单机版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
string s;
cin >>s;
int n =s.size();
vector<vector<bool>> c(n, vector<bool>(n, false));
for(int i =1; i<=n; i++)
{
for(int j =0; j+i-1<n; j++)
{
int l =j, r =j+i -1;
c[l][r] = s[l] ==s[r] &&(l+1 > r-1 || c[l+1][r-1]);
}
}
vector<int> f(n+1);
f[0]= 0;
for(int i =1; i<=n; i++)
{
f[i] =INT_MAX;
for(int j =1; j<=i; j++)
if(c[j-1][i-1]) f[i] =min(f[i], f[j-1] +1);
}
cout<< f[n]-1<<endl;
return 0;
}
|
Longest Common Subsequence
最长公共子序列。dp 思想，注意边界处理。时间复杂度是$O(mn)$，空间复杂度是$O(mn)$，其中$m$, $n$ 分别是字符串1和字符串2的长度。.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n =text1.size(), m =text2.size();
if(n ==0 || m ==0) return 0;
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i =1; i<= n; i++)
for(int j =1; j<= m; j++)
if(text1[i-1] ==text2[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[n][m];
}
};
|
Longest Common Substring
时间复杂度 $O(mn)$，空间复杂度$O(mn)$ 其中$m$, $n$ 分别是字符串1和字符串2的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def longestSubstring(str1, str2):
if not str1 or not str2: return 0
n, m =len(str1), len(str2)
dp =[[0]*(m) for _ in range(n)]
_max =0
for i in range( n):
for j in range( m):
if(str1[i] ==str2[j]):
if i ==0 or j ==0:
dp[i][j] =1
else:
dp[i][j] =dp[i-1][j-1] +1
_max =max(_max, dp[i][j])
else:
dp[i][j] =0
return _max
str1 ="GeeksforGeeks"
str2 ="GeeksQuiz"
print(longestSubstring(str1, str2))
|
Longest Common Prefix
暴力求解法，时间复杂度是$ O(n* minLength)$， 其中 $n $是字符串的个数 strs.size(). 并且其他的优化方法比如 trie 不见得能够降低时间复杂度。需要关注 str.size() 或者是 str.length() 都是需要转换成 int 然后再进行 min的计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size() ==0)
return "";
int min_len = strs[0].length();
for(int i =1; i< strs.size() ; i++)
min_len= min(min_len, int(strs[i].size()));
for(int s =1; s <= min_len ; s++)
{
char ch =strs[0][s -1];
for(int i =1; i< strs.size() ; i++)
if(strs[i][s -1] != ch)
return strs[0].substr(0, s -1);
}
return strs[0].substr(0, min_len);
}
};
|
python的写法还是比较简洁易懂的。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ''
shortest =min(strs, key =len)
for i, w in enumerate(shortest):
for j in range(len(strs)):
if w != strs[j][i]:
return shortest[:i]
return shortest
|
64. Minimum Path Sum
动态规划可以用来被求解最小值，dp[i][j] 表示到大 grid[i][j] 所经过的最小的路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() ==0 || grid[0].size() ==0)
return 0;
int m = grid.size(), n =grid[0].size();
vector<vector<int>> f(m, vector<int>(n, 0));
// 初始化
f[0][0] =grid[0][0];
for(int i =1; i<m; i++) f[i][0] =f[i-1][0] + grid[i][0];
for(int i =1; i<n; i++) f[0][i] =f[0][i-1] + grid[0][i];
// 转移方程
for(int i =1;i <m; i++)
for(int j =1; j< n; j++)
f[i][j] =min(f[i-1][j], f[i][j-1]) + grid[i][j];
return f[m-1][n -1];
}
};
|