动态规划与练习题
一.什么是动态规划？
动态规划（Dynamic Programming）是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。
在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
对于DP，有三个特点：
1. 把原来的问题分解成了几个相似的子问题。 2. 所有的子问题都只需要解决一次。 3. 储存子问题的解
其本质就是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。
动态规划问题一般从以下四个角度考虑：
1. 状态定义 2. 状态间的转移方程定义 3. 状态的初始化 4. 返回结果
状态定义的要求：定义的状态一定要形成递推关系。
一句话概括：三特点四要素两本质。
适用场景：最大值/最小值, 可不可行, 是不是，方案个数
二.题目
1.题目：斐波那契数列
题目描述：
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。 斐波那契数列是一个满足 fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.fib(x)={1fib(x−1)+fib(x−2)x=1,2x>2 的数列 数据范围：1\leq n\leq 401≤n≤40 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ，本题也有时间复杂度 O(logn)O(logn) 的解法
分析：拿到这道题，我们一般都会想到使用递归法来做，递归做这道题很简单。
class Solution {
public:
int Fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
};但是我们要知道，递归的话，当n等于50或者更大的时候，就可能会出现栈溢出，时间慢等问题，显然，递归是不可行的。
我们使用动态规划来解决问题：
首先分析一下其状态、状态转移方程、初始状态和结果如何：
①状态F[i]：第i项的值。就是当前我们所获得的结果的状态如何？ ②状态转移方程：F[i] = F[i-1]+F[i-2]。就是我们如何去获得结果 ③初始状态：F[0] = 0,F[1] = 1 ④返回结果：F[n]
class Solution {
public:
int Fibonacci(int n) {
int* F = new int[n + 1];
F[0] = 0, F[1] = 1;//初始状态
for (int i = 2; i <= n; i++)
{
F[i] = F[i - 1] + F[i - 2];//状态转移方程
}
return F[n];
}
};当然，我们也可以不要创建数组，优化一下空间复杂度，使用两个临时变量替代数组，两个临时变量用来动态更新状态即可。
class Solution {
public:
int Fibonacci(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
int a = 0, b = 1;
int fab;
for (int i = 2; i <= n; i++)
{
fab = a + b;
a = b;
b = fab;
}
return fab;
}
};2.题目：字符串分割
题目描述：
给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。 例如: 给定s=“nowcode”； dict=["now", "code"]. 返回true，因为"nowcode"可以被分割成"now code".
分析：
对于字符串s，我们很容易想到如何去寻找单词：也就是说，我们确定F[i]（前i个字符组成的单词）以及substr[i+1,j]（从第i+1到j个字符），那就true了。那么就有下面的过程：
如例中的：
j<i && F[1] && substr[2,6] j<i && F[2] && substr[3,6] j<i && F[3] && substr[4,6] ...... j<i && F[5] && substr[6,6] 逐个去判断
如此，我们就能知道状态转换方程就是：i<j && F[i] && substr[i+1,j]
初始状态如何？我们需要返回的结果是bool型，我们使用数组来存放子问题的结果。那么，第一个判断的时候，由于使用的是逻辑与，所以初始化为true。
最后，返回的结果就是F[s.size()];
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
if(s.empty())
return false;
if(dict.empty())
return false;
vector<bool> b(s.size()+1,false);
b[0]=true;
for(int i = 1;i<=s.size();i++)
{
for(int j = i-1 ; j >=0 ;j-- )
{
if(b[j] && dict.find(s.substr(j,i-j))!=dict.end())
{
b[i] = true;
break;
}
}
}
return b[s.size()];
}
};3.题目：三角矩阵
题目描述：
给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
例如，给出的三角形如下：
[[20],[30,40],[60,50,70],[40,10,80,30]]最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。
注意：
如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。
分析：
从上到下，我们通过分析，可以得知在每一层中找最小的时候，需要判断边界和非边界的情况。如果是非边界，那么就需要找出上一层相邻的两个值中最小的一个，然后相加，如果是边界，因为只有同样是边界的上一层的值才能与之相邻，那么就直接与上一层的这条边界的值相加。依次往下走就可以了。
代码如下：
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
if(triangle.empty())//判空
{
return 0;
}
int row = triangle.size(),col = triangle[0].size();
for(int i = 1;i<row;i++)//循环每一行
{
for(int j = 0;j<=i;j++)//循环每一列
{
if(j==0)//边界
triangle[i][j] = triangle[i-1][0]+triangle[i][j];
else if(j==i)//边界
{
triangle[i][j] = triangle[i-1][j-1]+triangle[i][j];
}
else//非边界
{
triangle[i][j] = min(triangle[i-1][j-1],triangle[i-1][j])+triangle[i][j];
}
}
}
int min_val = triangle[row-1][0];//在三角形的最后一行找最小，最小的就是结果
for(int i = 1;i<row;i++)//三角形最后一行的数据的个数(列)就是三角形的行数row
{
min_val = min(min_val,triangle[row-1][i]);//找到最小值
}
return min_val;
}
};如果我们是从下往上走，就不需要考虑边界问题了，因为从下往上，都会有两个值与之相邻，不需要额外判断边界相邻问题了。最后只需要返回F(0,0);
代码如下：
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
if(triangle.empty())//判空
{
return 0;
}
int row = triangle.size(),col = triangle[0].size();
for(int i = row-2;i>=0;--i)//循环每一行
{
for(int j = 0;j<=i;j++)//循环每一列
{
triangle[i][j] = min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
}
}
return triangle[0][0];
}
};4.题目：路径总数
题目描述：
一个机器人在m×n大小的地图的左上角（起点）。 机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。 可以有多少种不同的路径从起点走到终点？
备注：m和n小于等于100,并保证计算结果在int范围内 数据范围：0 < n,m \le 1000<n,m≤100，保证计算结果在32位整型范围内 要求：空间复杂度 O(nm)O(nm)，时间复杂度 O(nm)O(nm) 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(min(n,m))O(min(n,m))
分析：对于状态，我们必须保证它是一个子问题，然后我们随便找一个点(i,j)，题目中说了，每次只能向右和向下走，那么对于从起点(0,0)到(i,j),到达(i,j)的路径只有两条，就是(i,j-1)和(i-1,j)。所以我们就找到了状态和状态转移方程:
状态：从(0,0)到(i,j)的路径总数 状态转移方程：F(i,j) = F(i-1,j)+F(i,j-1)
有个特殊情况是(i,0)和(0,j)，他们只能向下或向右，所以只有一条路，所以F(i,0) = 1,F(0,j) = 1
初始化：F(i,0) = 1,F(0,j) = 1
子问题的结果不断存储到数组中，到达了数组最后一个位置，就是结果
返回结果:F(n-1,m-1)
代码如下：
class Solution {
public:
/**
*
* @param m int整型
* @param n int整型
* @return int整型
*/
int uniquePaths(int m, int n) {
// write code here
if(m<1 || n<1)
{
return 0;
}
vector<vector<int>> pathNum(m,vector<int>(n,1));
for(int i = 1;i<m;i++)
{
for(int j = 1;j<n;j++)
{
pathNum[i][j] = pathNum[i-1][j]+pathNum[i][j-1];
}
}
return pathNum[m-1][n-1];
}
};5.题目：最小路径和
题目描述：
给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。 注意：你每次只能向下或向右移动。
分析：
这道题可以说是第三题和第四题的结合。从(0,0)到(i,j)的路径总和的最小值，然后每一次都选向下走或向右走之后的最小值，这样就行了，总体思路与第四题差不多。
代码如下：
class Solution {
public:
/**
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
int minPathSum(vector<vector<int> >& grid) {
// write code here
if(grid.size()==0)
{
return 0;
}
int row = grid.size();
int col = grid[0].size();
vector<vector<int>> minNum(row,vector<int>(col));
minNum[0][0] = grid[0][0];
for(int i = 1;i<row;i++)
{
minNum[i][0] = minNum[i-1][0]+grid[i][0];
}
for(int j = 1;j<col;j++)
{
minNum[0][j] = minNum[0][j-1]+grid[0][j];
}
for(int i = 1;i<row;i++)
{
for(int j = 1;j<col;j++)
{
minNum[i][j] = min(minNum[i-1][j],minNum[i][j-1])+grid[i][j];
}
}
return minNum[row-1][col-1];
}
};6.题目：背包问题
题目描述：
有
n个物品和一个大小为m的背包. 给定数组A表示每个物品的大小和数组V表示每个物品的价值. 问最多能装入背包的总价值是多大?
A[i], V[i], n, m均为整数- 你不能将物品进行切分
- 你所挑选的要装入背包的物品的总大小不能超过
m - 每个物品只能取一次
- m <= 1000m<=1000\
len(A),len(V)<=100len(A),len(V)<=100
分析：
先分析一下状态：
对于背包问题，我们需要明白每一个物品对应的体积大小和价值大小： 价值大，体积小 价值大，体积大 价值小，体积小 价值小，体积大 那么，如果我们需要定义出状态，那么就是F(i,j):表示前i个物品，在容量为j的背包中的最大价值。
接着是状态转移方程：
对于每次放一个新物品，我们都需要考虑以下情况： ①需要放进的物品的体积小于或等于背包剩余的容量 这个情况，需要看看选择放还是不放 若是放：F(i,j) = F(i-1,j-A(i-1))+V(i-1) 若是不放：F(i,j) = F(i-1,j) 最后基于这两种情况取最大值。 ②需要放进的物品的体积大于背包剩余的容量 F(i,j) = F(i-1,j) 这里需要解释的是，F中的i和j与A和V中的i和j是指向同一个物品，原因是在创建二维数组的时候，我们需要额外多加一行一列，因为需要对其进行初始化成0，初始化成0的目的是，我们在判断上面第一种情况，并且是放物品的情况下，需要减去这个物品的体积，得到剩余的背包容量和其对应的物品的价值，最后于这个物品的价值相加在一起。如果这个物品的体积与当前背包容量相减后恰好为0，那么此时的背包的物品的价值自然为0，需要额外多加一行一列来存储这个值，这也是初始值的定义。
初始值：
额外加的F(i,0)和F(j,0)全部初始化为0，当然，其余位置也可以初始化为0，只是F(i,0)和F(j,0)这一行是不变了。
返回结果
设背包最大容量为m==11，那么我们在找背包能够装的物品的最大价值的过程，是从m==1开始，化成子问题，一个个存储到数组中，那么自然到m==11，也就是最后的那个位置，就是最终结果了。 F(n,m)
代码如下：
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param a: Given n items with size A[i]
* @param v: Given n items with value V[i]
* @return: The maximum value
*/
int backPackII(int m, vector<int> &a, vector<int> &v) {
// write your code here
if(m<0 || a.empty()||v.empty())
{
return 0;
}
int N= a.size()+1;
int M = m+1;
vector<vector<int>> result;
result.resize(N);
//初始化为0
for(int i = 0;i<N;i++)
{
result[i].resize(M,0);
}
for(int i = 1;i<N;i++)
{
for(int j = 1;j<M;j++)
{
if(a[i-1]<=j)
{
result[i][j] = max(result[i-1][j],result[i-1][j-a[i-1]]+v[i-1]);
}
else{
result[i][j] = result[i-1][j];
}
}
}
return result[N-1][m];
}
};当然，也有一维数组的做法，这个做法更加的简洁，不同的是，需要从尾开始走，因为后面的元素更新需要依靠前面的元素未更新（模拟二维矩阵的上一行的值）的值
class Solution {
public:
int backPackII(int m, vector<int> &a, vector<int> &v) {
// write your code here
if(m<0 || a.empty()||v.empty())
{
return 0;
}
int N= a.size();//不需要额外+1
int M = m+1;
vector<int> result;
result.resize(M,0);
//初始化为0
for(int i = 0;i<N;i++)
{
for(int j = M-1;j>0;j--)
{
if(a[i]<=j)
{
result[j] = max(result[j],result[j-a[i]]+v[i]);
}
else{
result[j] = result[j];
}
}
}
return result[m];
}
};腾讯云开发者
