devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++【算法】【动态规划问题】_c++多短途的最小成本问题的动态规划算法实现

作者：小惠珠哦 | 2024-07-21 23:02:35

赞

踩

c++多短途的最小成本问题的动态规划算法实现

目录

一、斐波那契数列

二、字符串分割

三、三角矩阵​​​​​​​

四、路径总数​​​​​​​

五、最小路径和

六、背包问题

七、回文串分隔

八、编辑距离

九、不同子序列

动态规划是在将大问题转化为小问题的分治过程中，保存对这些小问题已经处理好的结果，并提供给后面处理更大的问题来使用这些结果

动态规划的三个特点

1.把原来的问题分解成了几个相似的子问题

2.所有的子问题都只需要解决一次

3.存储子问题的解

动态规划的本质，是对问题状态的定义和状态转移方程的定义（状态以及状态之间的递推关系）

动态规划问题一般从以下四个角度考虑：

1.状态定义

2.状态间的转移方程定义（从题目中找线索）

3.状态的初始化

4.返回结果

状态定义的要求：定义的状态一定要形成递推关系

难点：状态比较难以定义，转移方程不好找。

适用场景：最大值/最小值，可不可行，是不是，方案个数。

一、斐波那契数列

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。 

斐波那契数列是一个满足 fib(x)={1x=1,2fib(x−1)+fib(x−2)x>2fib(x)={1fib(x−1)+fib(x−2)​x=1,2x>2​ 的数列 

数据范围：1≤n≤401≤n≤40

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ，本题也有时间复杂度 O(logn)O(logn) 的解法 

输入描述：

一个正整数n

返回值描述：

输出一个正整数。

示例1

输入：

4

复制返回值：

3

复制说明：

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。

示例2

输入：

1

复制返回值：

1

复制

示例3

输入：

2

复制返回值：

1

递归的解法 

  1. class Solution {
  2. public:
  3.     int Fibonacci(int n) {
  4.         if(n==0)
  5.             return 0;
  6.         if(n==1||n==2)
  7.             return 1;
  8.         return Fibonacci(n-1)+Fibonacci(n-2);
  9.     }
  10. };

如果这一个n非常大的话，上面递归的算法的时间复杂度会非常大，一次递归分解成两个，两次分解成四个，复杂度呈指数级增长。

状态F(i)：第i项的值

状态转移方程（从已知的结果推导未知的结果）：F(i)=F(i-1)+F(i-2)

初始状态：F(0)=0,F(1)=1

求解：第n项的结果

返回结果F(n)：F(n)

  1. class Solution {
  2. public:
  3.     int Fibonacci(int n) {
  4.         //创建一个数组，保存中间状态的解
  5.         int * F=new int[n+1];
  6.         //初始化F(0)和F(1)
  7.         F[0]=0;
  8.         F[1]=1;
  9.         //F[i]=F[i-1]+F[i-2]
  10.         for(int i=2;i<=n;++i)
  11.         {
  12.             F[i]=F[i-1]+F[i-2];
  13.         }
  14.         //返回结果
  15.         return F[n];
  16.     }
  17. };

上面是数组的写法，还可以进一步优化空间复杂度至O（1）

  1. class Solution {
  2. public:
  3.     int Fibonacci(int n) {
  4.         if(n==0||n==1)
  5.         {
  6.             return n;
  7.         }
  8.  
  9.         int fn;
  10.         int fn1=1;
  11.         int fn2=0;
  12.         for(int i=2;i<=n;++i)
  13.         {
  14.             fn=fn1+fn2;
  15.             //更新中间状态
  16.             fn2=fn1;
  17.             fn1=fn;
  18.         }
  19.         return fn;
  20.     }
  21. };

二、字符串分割

拆分词句_牛客题霸_牛客网

给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。 

例如:
给定s=“nowcode”；
dict=["now", "code"].
返回true，因为"nowcode"可以被分割成"now code".

问题：字符串s是否可以被分割  -->抽象状态

状态：字符串的前i个字符是否可以被分割

F(3):前三个字符是否可以被分割：true

F(7):F(3)&&[4,7]是否可以在词典中找到 

F(1)&&[2,7]

F(2)&&[3,7]

F(3)&&[4,7]

F(4)&&[5,7]

F(5)&&[6,7]

F(6)&&[7,7]

[0,0]&&[1,8] -->整体能不能被匹配到

 状态转移方程：F(i) ：j<i &&F(j)&&[j+1,i]是否可以在词典中找到

初始状态：F(0)

返回结果：F(字符串长度）：f(s.size()) f(s.size())

  1. class Solution {
  2.   public:
  3.     bool wordBreak(string s, unordered_set<string>& dict) {
  4.         if (s.empty()) {
  5.             return false;
  6.         } 
  7.         if (dict.empty()) {
  8.             return false;
  9.         } 
  10.         vector<bool> can_break(s.size() + 1, false);
  11. // 初始化F(0) = true
  12.         can_break[0] = true;
  13.         for (int i = 1; i <= s.size(); i++) {
  14.             for (int j = i - 1; j >= 0; j--) {
  15. // F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false
  16. // 第j+1个字符的索引为j
  17.                 if (can_break[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
  18.                     can_break[i] = true;
  19.                     break;
  20.                 }
  21.             }
  22.         } 
  23.         return can_break[s.size()];
  24.     }
  25. };

三、三角矩阵

三角形_牛客题霸_牛客网

描述

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字， 

例如，给出的三角形如下： 

[[20],[30,40],[60,50,70],[40,10,80,30]]

也就是：

                        [[20],

                      [30,40],

                    [60,50,70],

                 [40,10,80,30]]

最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。注意： 

如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。

从上往下走

问题：从顶部到底部的最小路径和

状态F(i,j)：从(0,0)到(i,j)的最小路径和

状态转移方程：

(0<j<i)

F(i,j)=min(F(i-1,j-1),F(i-1,j))+array[i][j]

(j==0||j==i):F(i,j)

        j==0:F(i-1,0)+array[i][0]

        j==i:F(i-1,j-1)+array[i][j]

F(1,0):F(0,0)+array[1][0]      F(1,1):F(0,0)+array[1][1]

F(2,1):min(F(1,0),F(1,1))+array[2][1]

 (i,j)-->(i+1,j)和(i+1,j+1)

(i-1,j-1)和(i-1,j) --->(i,j)

初始状态：F(0,0)=array[0][0]

返回结果：min(F(row-1,j))

  1. class Solution {
  2. public:
  3.     int minimumTotal(vector<vector<int> > &triangle) {
  4.         if(triangle.empty())
  5.             return 0;
  6.         int row=triangle.size();
  7.         int col=triangle[0].size();
  8.         //第0行不用考虑，考虑从1开始
  9.         for(int i=1;i<row;++i)
  10.         {
  11.             for(int j=0;j<=i;++j)
  12.             {
  13.                 //处理边界的情况
  14.                 //因为边界的情况只有一条路可以走
  15.                 if(j==0)
  16.                 {
  17.                     triangle[i][j]=triangle[i-1][j]+triangle[i][j];
  18.                 }
  19.                 else if(j==i)
  20.                 {
  21.                     triangle[i][j]=triangle[i-1][j-1]+triangle[i][j];
  22.                 }
  23.                 //三角形非边界的情况
  24.                 else
  25.                 {
  26.                     triangle[i][j]=min(triangle[i-1][j-1],triangle[i-1][j])+triangle[i][j];
  27.                 }
  28.             }
  29.         }
  30.         int minSum=triangle[row-1][0];
  31.         for(int j=1;j<row;++j)
  32.             minSum=min(minSum,triangle[row-1][j]);
  33.         return minSum;
  34.     }
  35. };

从下往上走的情况

状态F(i,j)：从(i,j)到达最后一行的最小路径和

状态转移方程：F(i,j)：min(F(i+1,j),F(i+1,j+1))+array[i][j]

初始状态：F(row-1,j)=array[row-1][j]

返回结果：F(0,0)

  1. class Solution {
  2. public:
  3.     int minimumTotal(vector<vector<int> > &triangle) {
  4.         if(triangle.empty())
  5.             return 0;
  6.         //F(row-1,j)=array[row-1][j]
  7.         int row=triangle.size();
  8.         for(int i=row-2;i>=0;--i)
  9.         {
  10.             for(int j=0;j<=i;++j)
  11.             {
  12.                 triangle[i][j]=min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
  13.             }
  14.         }
  15.         return triangle[0][0];
  16.     }
  17. };

四、路径总数

不同路径的数目(一)_牛客题霸_牛客网

描述

一个机器人在m×n大小的地图的左上角（起点）。 

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？ 

备注：m和n小于等于100,并保证计算结果在int范围内 

数据范围：0<n,m≤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))

示例1

输入：

2,1

复制返回值：

1

复制

示例2

输入：

2,2

复制返回值：

2

状态F(i,j)：从(0,0)到达(i,j)的路径个数

状态转移方程：F(i,j)： F(i,j-1)+F(i-1,j)

初始状态：F(i,0)=F(0,j)=1

返回：F(m-1,n-1)

  1.  
  2. class Solution {
  3.   public:
  4.     /**
  5.      *
  6.      * @param m int整型
  7.      * @param n int整型
  8.      * @return int整型
  9.      */
  10.     int uniquePaths(int m, int n) {
  11.         if (m < 1 || n < 1) {
  12.             return 0;
  13.         } 
  14.         // 申请F(i, j)空间，初始化
  15.         vector<vector<int> > ret(m, vector<int>(n, 1));
  16.         for (int i = 1; i < m; ++i) {
  17.             for (int j = 1; j < n; ++j) {
  18. // F(i,j) = F(i-1,j) + F(i,j-1)
  19.                 ret[i][j] = ret[i - 1][j] + ret[i][j - 1];
  20.             }
  21.         } 
  22.         return ret[m - 1][n - 1];
  23.     }
  24. };

五、最小路径和

带权值的最小路径和_牛客题霸_牛客网

描述

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。
注意：你每次只能向下或向右移动。

示例1

输入：

[[1,2],[5,6],[1,1]]

复制

返回值：

状态F(i,j)：从(0,0)到达(i,j)的最短路径和

转移方程：

        F(i,j)：min(F(i,j-1),F(i-1,j))+array[i][j]

        第一行：

        F(0,j)：F(0,j-1)+array[0][j]

        第一列

         F(i,0)：F(i-1,0)+array[i][0]

初始状态：

        F(0,0)=array[0][0]

返回：F(row-1,col-1)

  1.  
  2. class Solution {
  3. public:
  4.     /**
  5.      * 
  6.      * @param grid int整型vector<vector<>> 
  7.      * @return int整型
  8.      */
  9.     int minPathSum(vector<vector<int> >& grid) {
  10.         // write code here
  11.         if(grid.size()==0)
  12.         {
  13.             return 0;
  14.         }
  15.         int row=grid.size();
  16.         int col=grid[0].size();
  17.         //第一行
  18.         for(int i=0;i<col;++i)
  19.         {
  20.             grid[0][i]=grid[0][i-1]+grid[0][i];
  21.         }
  22.         //第一列
  23.         for(int i=1;i<row;++i)
  24.         {
  25.             grid[i][0]=grid[i-1][0]+grid[i][0];
  26.         }
  27.         for(int i=1;i<row;++i)
  28.         {
  29.             for(int j=1;j<col;++j)
  30.             {
  31.                 grid[i][j]=min(grid[i][j-1],grid[i-1][j])+grid[i][j];
  32.             }
  33.         }
  34.         return grid[row-1][col-1];
  35.     }
  36. };

六、背包问题

 LintCode 炼码

描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

  1. A[i], V[i], n, m 均为整数
  2. 你不能将物品进行切分
  3. 你所挑选的要装入背包的物品的总大小不能超过 m
  4. 每个物品只能取一次
  5. m<=1000m<=1000\

len(A),len(V)<=100len(A),len(V)<=100

样例 1：

输入：

 
 
  1. m = 10
  2. A = [2, 3, 5, 7]
  3. V = [1, 5, 2, 4]
 
 
输出：
 
 
 
 
9
 
 
解释：
 
 
装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9
 
 
样例 2：
 
 
输入：
 
 
 
 
  1. m = 10
  2. A = [2, 3, 8]
  3. V = [2, 5, 8]
 
 
输出：
 
 
 
 
10
 

 

 
 
价值大，体积大
 
 
价值大，体积小
 
 
价值小，体积大
 
 
价值小，体积小
 

 

 
 
状态F(i,j)：从前i个商品中选择，包的大小为j时的最大值 
 
 
状态索引范围：从1开始，价值数组，大小数组索引范围：从0开始
 
 
状态转移方程：
 
 
如果第i个商品的大小A[i-1]<=j，就可以将商品放进去（j是我们当前包剩余的大小）
 
 
        F(i,j)：F(i-1)+V[i-1]
 
 
第i个商品可以放入大小为j的包中：
 
 
        F(i, j) = max{F(i-1,j), F(i-1, j - A[i]) + V[i]}
         F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
         F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放第i个商品。
 
 
第i个商品太大，(A[i-1]>j)大小为j的包放不下第i个商品
 
 
        F(i,j)=F(i-1,j)
 
 
初始状态：
 
 
        第零行表示我现在没有放置任何的商品，第零列表示我现在的包里面放不下任何的商品
 
 
        F(i,0)=0
 
 
        F(0,j)=0
 
 
 

 

采用二维数组的写法 
 

  1. int backPackII(int m, vector<int> A, vector<int> V) {
  2.     if (A.empty() || V.empty() || m < 1) {
  3.         return 0;
  4.     } 
  5.     //多加一行一列，用于设置初始条件
  6.     const int N = A.size() + 1;
  7.     const int M = m + 1;
  8.     vector<vector<int> > result;
  9.     result.resize(N);
  10. //初始化所有位置为0，第一行和第一列都为0，初始条件
  11.     for (int i = 0; i != N; ++i) {
  12.         result[i].resize(M, 0);
  13.     } 
  14.     for (int i = 1; i < N; ++i) {
  15.         for (int j = 1; j != M; ++j) {
  16. //第i个商品在A中对应的索引为i-1: i从1开始
  17. //如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
  18.             if (A[i - 1] > j) {
  19.                 result[i][j] = result[i - 1][j];
  20.             } 
  21.             //如果可以装下，分两种情况，装或者不装
  22. //如果不装，则即为(i-1, j)
  23. //如果装，需要腾出放第i个物品大小的空间： j - A[i-1],装入之后的最大价值即为(i - 1, j- A[i-1]) + 第i个商品的价值V[i - 1]
  24. //最后在装与不装中选出最大的价值
  25.             else {
  26.                 int newValue = result[i - 1][j - A[i - 1]] + V[i - 1];
  27.                 result[i][j] = max(newValue, result[i - 1][j]);
  28.             }
  29.         }
  30.     } 
  31.     //返回装入前N个商品，物品大小为m的最大价值
  32.     return result[N - 1][m];
  33. }
 

 采用一维数组的写法
 

  1. #include <iostream>
  2. using namespace std;
  3. int backPackII(int m, vector<int> A, vector<int> V) {
  4.     if (A.empty() || V.empty() || m < 1) {
  5.         return 0;
  6.     } 
  7.     const int N = A.size();
  8. //多加一列，用于设置初始条件，因为第一件商品要用到前面的初始值
  9.     const int M = m + 1;
  10.     vector<int> result;
  11. //初始化所有位置为0，第一行都为0，初始条件
  12.     result.resize(M, 0);
  13.     //这里商品的索引位置不需要偏移，要和未优化的方法区分开
  14. //这里的i-1理解为上一行，或者未更新的一维数组值
  15.     for (int i = 0; i != N; ++i) {
  16.         for (int j = M - 1; j > 0; --j) {
  17. //如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
  18.             if (A[i] > j) {
  19.                 result[j] = result[j];
  20.             } 
  21.             //如果可以装下，分两种情况，装或者不装
  22. //如果不装，则即为(i-1, j)
  23. //如果装，需要腾出放第i个物品大小的空间： j - A[i],装入之后的最大价值即为(i - 1, j -
  24.             A[i-1]) + 第i个商品的价值V[i]
  25. //最后在装与不装中选出最大的价值
  26.             else {
  27.                 int newValue = result[j - A[i]] + V[i];
  28.                 result[j] = max(newValue, result[j]);
  29.             }
  30.         }
  31.     } 
  32.     //返回装入前N个商品，物品大小为m的最大价值
  33.     return result[m];
  34. }
 

七、回文串分隔
 

 
 
分割回文串-ii_牛客题霸_牛客网
 

 

 
 
描述
 
 
给出一个字符串s，分割s使得分割出的每一个子串都是回文串 
 
 
计算将字符串s分割成回文分割结果的最小切割数 
 
 
例如:给定字符串s="aab",
 
 
返回1，因为回文分割结果["aa","b"]是切割一次生成的。
 
 
示例1
 
 
输入：
 
 
"aab"
 
 
复制返回值：
 
 
1

 

 

 
 
问题：s的最小分割次数
 
 
状态F(i)：s的前i个字符最小的分割次数
 
 
状态转移方程：（移步转移只能切一次）
 
 
        F(i):j<i &&[j+1,i]是回文串，min(F(j)+1)
 
 
        F(i):[1,i]是回文串：0
 
 
 
 
“aab”
 
 
F(1):0
 
 
F(2):整体0
 
 
F(3):F(2)（前面两个字符最小分割次数已经决定了，我F(3)不用管，就直接在F(2)后面再切一刀就行）（aa | b）
 
 
 
 
初始状态：
 
 
        F(i)=i-1（i个字符最多分割i-1次）
 
 
        
 

 

  1.  
  2. class Solution {
  3. public:
  4.     /**
  5.      * 
  6.      * @param s string字符串 
  7.      * @return int整型
  8.      */
  9.     bool isPal(string& s,int start,int end)
  10.      {
  11.          while(start<end)
  12.          {
  13.              if(s[start]!=s[end])
  14.              {
  15.                  return false;
  16.              }
  17.              ++start;
  18.              --end;
  19.          }
  20.          return true;
  21.     }
  22.     int minCut(string s) {
  23.         // write code here
  24.  
  25.         int len=s.size();
  26.         if(len==0)
  27.             return 0;
  28.         //判断整体是不是一个回文串
  29.         if(isPal(s,0,len-1))
  30.             return 0;
  31.  
  32.         vector<int> minCut(len+1);
  33.         //F(i)=i-1
  34.         //5个字符中间最多分割4次
  35.         for(int i=1;i<=len;++i)
  36.             minCut[i]=i-1;
  37.         for(int i=2;i<=len;++i)
  38.         {
  39.             //整体是否为回文串
  40.             if(isPal(s,0,i-1))
  41.             {
  42.                 minCut[i]=0;
  43.                 continue;
  44.             }
  45.             // j<i&&[j+1,i]是否为回文串
  46.             for(int j=1;j<i;++j)
  47.             {
  48.                 if(isPal(s,j,i-1))
  49.                 {
  50.                     minCut[i]=min(minCut[i],minCut[j]+1);
  51.                 }
  52.             }
  53.             
  54.         }
  55.         return minCut[len];
  56.     }
  57. };
 

或者将0的位置也利用起来，写下面这种写法，就将整体是否为回文串和局部是否为回文串的情况归并到一起了
 

  1.  
  2. class Solution {
  3. public:
  4.     /**
  5.      * 
  6.      * @param s string字符串 
  7.      * @return int整型
  8.      */
  9.     bool isPal(string& s,int start,int end)
  10.      {
  11.          while(start<end)
  12.          {
  13.              if(s[start]!=s[end])
  14.              {
  15.                  return false;
  16.              }
  17.              ++start;
  18.              --end;
  19.          }
  20.          return true;
  21.     }
  22.     int minCut(string s) {
  23.         // write code here
  24.  
  25.         int len=s.size();
  26.         if(len==0)
  27.             return 0;
  28.         if(isPal(s,0,len-1))
  29.             return 0;
  30.         vector<int> minCut(len+1);
  31.         //F(i)=i-1
  32.         for(int i=0;i<=len;++i)
  33.             minCut[i]=i-1;
  34.         for(int i=2;i<=len;++i)
  35.         {
  36.             // j<i&&[j+1,i]是否为回文串
  37.             for(int j=0;j<i;++j)
  38.             {
  39.                 if(isPal(s,j,i-1))
  40.                 {
  41.                     minCut[i]=min(minCut[i],minCut[j]+1);
  42.                 }
  43.             }
  44.             
  45.         }
  46.         return minCut[len];
  47.     }
  48. };
 

 但是上面的主代码中存在O(n^2)，并且其中调用的判断是否为回文串还有一层循环，为O(N^3)
 

我们可以保存这个区间是否为回文串
 

用一个n*n的方阵去保存下来，用空间换时间
 

 
 
判断回文串：
 
 
        状态F(i,j)：区间[i,j]是否为回文串
 
 
        状态转移方程：F(i,j)：s[i]==s[j] &&F(i+1,j-1)
 
 
        i==j：
 
 
                F(i,j)：true
 
 
        i+1==j：
 
 
                F(i,j)：s[i]==s[j]
 
 
初始状态：
 
 
        i==j:
 
 
        F(i,j):true
 

 

  1.  
  2. class Solution {
  3. public:
  4.     /**
  5.      * 
  6.      * @param s string字符串 
  7.      * @return int整型
  8.      */
  9.     bool isPal(string& s,int start,int end)
  10.      {
  11.          while(start<end)
  12.          {
  13.              if(s[start]!=s[end])
  14.              {
  15.                  return false;
  16.              }
  17.              ++start;
  18.              --end;
  19.          }
  20.          return true;
  21.     }
  22.     vector<vector<bool>> getMat(string & s)
  23.     {
  24.         int n=s.size();
  25.         vector<vector<bool>> Mat(n,vector<bool>(n,false));
  26.         for(int i=n-1;i>=0;--i)
  27.         {
  28.             for(int j=i;j<n;++j)
  29.             {
  30.                 if(j==i)
  31.                 {
  32.                     Mat[i][j]=true;
  33.                 }
  34.                 else if(j==i+1)
  35.                 {
  36.                     Mat[i][j]=s[i]==s[j];
  37.                 }
  38.                 else
  39.                 {
  40.                     Mat[i][j]=(s[i]==s[j])&&(Mat[i+1][j-1]);
  41.                 }
  42.             }
  43.         }
  44.         return Mat;
  45.     }
  46.     int minCut(string s) {
  47.         // write code here
  48.  
  49.         int len=s.size();
  50.         if(len==0)
  51.             return 0;
  52.         if(isPal(s,0,len-1))
  53.             return 0;
  54.         vector<int> minCut(len+1);
  55.         //F(i)=i-1
  56.         vector<vector<bool>> Mat=getMat(s);
  57.         for(int i=0;i<=len;++i)
  58.             minCut[i]=i-1;
  59.         for(int i=2;i<=len;++i)
  60.         {
  61.             // j<i&&[j+1,i]是否为回文串
  62.             for(int j=0;j<i;++j)
  63.             {
  64.                 if(Mat[j][i-1])
  65.                 {
  66.                     minCut[i]=min(minCut[i],minCut[j]+1);
  67.                 }
  68.             }
  69.             
  70.         }
  71.         return minCut[len];
  72.     }
  73. };
 

 

八、编辑距离
 

 
 
编辑距离_牛客题霸_牛客网
 

 

 
 
描述
 
 
给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。
 你可以对一个单词执行以下3种操作：
 a）在单词中插入一个字符
 b）删除单词中的一个字符
 c）替换单词中的一个字符
 
 
示例1
 
 
输入：
 
 
"b",""
 
 
复制返回值：
 
 
1

 
 
复制
 
 
示例2
 
 
输入：
 
 
"ab","bc"
 
 
复制返回值：
 
 
2 
 

 

 问题：word1到word2编辑距离
 

子问题：word1的局部变成word2局部需要的编辑距离
 

状态(i,j)：word1前i个字符到word2的前j个字符的编辑距离
 

状态转移方程：
 

        F(i,j)：min（插入，删除，替换）
 

                    min(F(i-1,j)+1,F(i,j-1)+1,F(i-1,j-1)+(w1[i]==w2[j]?0:1))
 

                    F(i,j-1)：（w1[1,i]-->w2[1,j-1]+插入-->F(i,j-1)+1-->F(i,j)
 

                    F(i-1,j)：w1[i,i-1]-->w2[1,j]+删除w1的第i个字符-->F(i-1,j)+1-->F(i,j)
 

                    F(i-1,j-1)：w1[1,i-1]->w2[1,j-1]+替换：w1[i]!=w2[j]-->F(i-1,j-1)+(w1[i]==w2[j]?0:1)
 

 
 
r:替换
 
 
i:插入
 
 
d:删除
 

 

""keji
"" 
i:"" ""
 
F(0,0):0
 		 
i:""+k-->k
 
F(0,1):1
 		 
i:""+ke
 
F(0,2):2
 		 
i:""+kej
 
F(0,3):3
 		 
i:""+keji
 
F(0,4):4
 
b 
d:b-b-->""
 
F(1,0):1
 		 
d:F(0,1)-->(删除b):b-->k
 
i : F(1,0)-->(插入k):b-->k
 
r:F(0,0)-->(b替换k):b-->k
 
F(1,1):1
 		 
d:F(0,2)-->(删除b):b-->ke
 
i :F(1,1)-->(插入e):b-->ke
 
r:F(0,1)-->(b替换e):b-->ke
 
F(1,2):2
 
i 
d:bi-bi-->""
 
F(2,0):2
 		 
d:F(1,1)-->(删除i):bi-->k
 
i :F(2,0)-->(插入k):bi-->k
 
r:F(1,0)-->(i替换k):bi-->k
 
F(2,1):2
 		 
d:F(1,2)-->(删除i):bi-->ke
 
i :F(2,1)-->(插入e):b-->k
 
r:F(1,1)-->(i替换e):bi-->ke
 
F(2,2):2（两次替换）
 
t 
d:bit-bit-->""
 
F(3,0):3
 
e 
d:bite-bite-->""
 
F(4,0):4
 
 

  1.  
  2. class Solution {
  3. public:
  4.     /**
  5.      * 
  6.      * @param word1 string字符串 
  7.      * @param word2 string字符串 
  8.      * @return int整型
  9.      */
  10.     int minDistance(string word1, string word2) {
  11.         // write code here
  12.         int row=word1.size();
  13.         int col=word2.size();
  14.  
  15.         vector<vector<int>> minD(row+1,vector<int>(col+1));
  16.         //初始化F(1,0):i  F(0,j):j 第一行和第一列
  17.         for(int i=0;i<=col;++i)
  18.         {
  19.             minD[0][i]=i;
  20.         }
  21.         for(int i=1;i<=row;++i)
  22.         {
  23.             minD[i][0]=i;
  24.         }
  25.         for(int i=1;i<=row;++i)
  26.         {
  27.             for(int j=1;j<=col;++j)
  28.             {
  29.                 //插入、删除
  30.                 //插入和删除的步数中选择一个步数最小的，然后+1
  31.                 minD[i][j]=min(minD[i][j-1],minD[i-1][j])+1;
  32.                 //替换
  33.                 //如果word1的第i个就等于word2的第j个，就不需要替换
  34.                 if(word1[i-1]==word2[j-1])
  35.                 {
  36.                     //替换是在对角线上
  37.                     minD[i][j]=min(minD[i][j],minD[i-1][j-1]);
  38.                 }
  39.                 else{
  40.                     //从插入删除和替换中选择一个步数最少的
  41.                     minD[i][j]=min(minD[i][j],minD[i-1][j-1]+1);
  42.                 }
  43.             }
  44.             
  45.         }
  46.         return minD[row][col];
  47.     }
  48. };
 

九、不同子序列
 

 
 
不同的子序列_牛客题霸_牛客网
 

 

 
 
描述
 
 
给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？ 
 
 
字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
 例如：
 
 
S="nowcccoder", T = "nowccoder" 
 
 
返回3 
 
 
示例1
 
 
输入：
 
 
"nowcccoder","nowccoder"
 
 
复制返回值：
 
 
3

 

 

 
 
问题：S中与T相同的子序列的个数
 
 
子问题：S的子串中与T相同的子序列的个数
 
 
状态F(i)：S的前i个字符构成的子串中与T前j个字符相同的子序列个数。
 
 
        子串的长度>=T的长度              
 
 
                        S:abaaaa            T:aba             i:4        F(i-1):1 -->aba   
 
 
                        第四个字符"a"与T的最后一个字符相同，然后取前面的字符找ab
 
 
        if(S[i]==T[j])
 
 
        :如果使用第i个字符，只能为子序列的最后一个字符，相当于和T的第j个字符匹配:F(i-1,j-1)
 
 
        :如果不使用第i个字符：F(i-1,j)
 
 
                F(i,j):
 
 
         F(i,j)：F(i-1,j-1)+F(i-1,j)
 
 
        if(S[i]!=T[j])
 
 
                ​​​​​​​肯定不能使用第i个字符
 
 
                F(i,j)=F(i-1,j)
 
 
        
 

 

 
 

rabbit
1（空的字符串中可以找到空的字符串）000000
r1 
1
 
F(0,0)+F(0,1)
 		 
0
 
 
a1 
1
 
F(1,1)
 		 
1
 
F(1,2)+F(1,1)
 
b1 
(rab中找ra)
 
b!=a
 
F(2,2)
 
1
 		 
b==b
 
F(2,2):ra-->ra:1
 
F(2,3):ra rab:0
 
b1
b1
i1
t1
 

 
 
初始状态F(i,0)=1（集合中寻找空集的个数）
 
 
                F(0,j)=0  (j!=0);
 

 

  1.  
  2. class Solution {
  3.   public:
  4.     /**
  5.      *
  6.      * @param S string字符串
  7.      * @param T string字符串
  8.      * @return int整型
  9.      */
  10.     int numDistinct(string S, string T) {
  11.         int s_size = S.size();
  12.         int t_size = T.size();
  13. // S的长度小于T长度，不可能含有与T相同的子串
  14.         if (S.size() < T.size()) return 0;
  15. // T为空串，只有空串与空串相同，S至少有一个子串，它为空串
  16.         if (T.empty()) return 1;
  17. // F(i,j)，初始化所有的值为0
  18.         vector<vector<int> > f(s_size + 1, vector<int>(t_size + 1, 0));
  19. // 空串与空串相同的个数为1
  20.         f[0][0] = 1;
  21.         for (int i = 1; i <= s_size; ++i) {
  22. // F(i,0)初始化
  23.             f[i][0] = 1;
  24.             for (int j = 1; j <= t_size; ++j) {
  25. // S的第i个字符与T的第j个字符相同
  26.                 if (S[i - 1] == T[j - 1]) {
  27.                     f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
  28.                 } 
  29.                 else {
  30. // S的第i个字符与T的第j个字符不相同
  31. // 从S的前i-1个字符中找子串，使子串与T的前j个字符相同
  32.                     f[i][j] = f[i - 1][j];
  33.                 }
  34.             }
  35.         } 
  36.         return f[s_size][t_size];
  37.     }
  38. };
 

由于我们这里观察到其实是要用到上一次遍历的结果，所以我们可以将二维矩阵降成一维的数组
 

  1.  
  2. class Solution {
  3.   public:
  4.     /**
  5.      *
  6.      * @param S string字符串
  7.      * @param T string字符串
  8.      * @return int整型
  9.      */
  10.     int numDistinct(string S, string T) {
  11.         if (S.empty())
  12.             return 0;
  13.         if (T.empty())
  14.             return 1;
  15.         int len1 = S.size();
  16.         int len2 = T.size();
  17.         vector<int> numDis(len2 + 1, 0);
  18.         numDis[0] = 1;
  19.         for (int i = 1; i <= len1; ++i) {
  20.             //从后向前更新，因为我们所需要使用的是未更新的值，也就是上一行的值
  21.             for (int j = len2; j > 0; --j) {
  22.                 if (S[i - 1] == T[j - 1])
  23.                     numDis[j] = numDis[j - 1] + numDis[j];
  24.             //如果相同的话，本一次更新就等于上一次的数据
  25.             }
  26.         } 
  27.         return numDis[len2];
  28.     }
  29. };
 

动态规划状态定义：
 

        状态来源：从问题中抽象状态
 

        抽象状态：每一个状态对应一个子问题
 

        状态的形式可以定义很多，如何验证状态的合理性：
 

                1.某一个状态的解或者多个状态处理之后的解能否对应最终问题的解。
 

                2.状态之间可以形成递推关系
 

        一维状态 VS 二维状态（依据问题和线索）
 

                首先尝试一维状态，
 

                一维的状态的合理性不满足的时候，再去定义二维状态。
 

        常见问题的状态：
 

                字符串：状态一般对应子串，状态中每一次一般增加一个新的字符
 

                矩阵：二维状态-->优化-->一维状态
 


                

        
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/862494
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号