目录

一、斐波那契数列

二、字符串分割

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

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

五、最小路径和

六、背包问题

七、回文串分隔

八、编辑距离

九、不同子序列

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

动态规划的三个特点

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

递归的解法 

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非常大的话，上面递归的算法的时间复杂度会非常大，一次递归分解成两个，两次分解成四个，复杂度呈指数级增长。

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

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

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

求解：第n项的结果

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

class Solution {
public:
    int Fibonacci(int n) {
        //创建一个数组，保存中间状态的解
        int * F=new int[n+1];
        //初始化F(0)和F(1)
        F[0]=0;
        F[1]=1;
        //F[i]=F[i-1]+F[i-2]
        for(int i=2;i<=n;++i)
        {
            F[i]=F[i-1]+F[i-2];
        }
        //返回结果
        return F[n];
    }
};

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

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0||n==1)
        {
            return n;
        }

        int fn;
        int fn1=1;
        int fn2=0;
        for(int i=2;i<=n;++i)
        {
            fn=fn1+fn2;
            //更新中间状态
            fn2=fn1;
            fn1=fn;
        }
        return fn;
    }
};

二、字符串分割

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

给定一个字符串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())

class Solution {
  public:
    bool wordBreak(string s, unordered_set<string>& dict) {
        if (s.empty()) {
            return false;
        } 
        if (dict.empty()) {
            return false;
        } 
        vector<bool> can_break(s.size() + 1, false);
// 初始化F(0) = true
        can_break[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
// F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false
// 第j+1个字符的索引为j
                if (can_break[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    can_break[i] = true;
                    break;
                }
            }
        } 
        return can_break[s.size()];
    }
};

三、三角矩阵

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

描述

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

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

[[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))

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty())
            return 0;
        int row=triangle.size();
        int col=triangle[0].size();
        //第0行不用考虑，考虑从1开始
        for(int i=1;i<row;++i)
        {
            for(int j=0;j<=i;++j)
            {
                //处理边界的情况
                //因为边界的情况只有一条路可以走
                if(j==0)
                {
                    triangle[i][j]=triangle[i-1][j]+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 minSum=triangle[row-1][0];
        for(int j=1;j<row;++j)
            minSum=min(minSum,triangle[row-1][j]);
        return minSum;
    }
};

从下往上走的情况

状态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)

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty())
            return 0;
        //F(row-1,j)=array[row-1][j]
        int row=triangle.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];
    }
};

四、路径总数

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

描述

一个机器人在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)

class Solution {
  public:
    /**
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        if (m < 1 || n < 1) {
            return 0;
        } 
        // 申请F(i, j)空间，初始化
        vector<vector<int> > ret(m, vector<int>(n, 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)
                ret[i][j] = ret[i - 1][j] + ret[i][j - 1];
            }
        } 
        return ret[m - 1][n - 1];
    }
};

五、最小路径和

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

描述

给定一个由非负整数填充的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)

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();
        //第一行
        for(int i=0;i<col;++i)
        {
            grid[0][i]=grid[0][i-1]+grid[0][i];
        }
        //第一列
        for(int i=1;i<row;++i)
        {
            grid[i][0]=grid[i-1][0]+grid[i][0];
        }
        for(int i=1;i<row;++i)
        {
            for(int j=1;j<col;++j)
            {
                grid[i][j]=min(grid[i][j-1],grid[i-1][j])+grid[i][j];
            }
        }
        return grid[row-1][col-1];
    }
};

六、背包问题

 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：

输入：

m = 10
A = [2, 3, 5, 7]
V = [1, 5, 2, 4]

输出：

9

解释：

装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9

样例 2：

输入：

m = 10
A = [2, 3, 8]
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

采用二维数组的写法 

int backPackII(int m, vector<int> A, vector<int> V) {
    if (A.empty() || V.empty() || m < 1) {
        return 0;
    } 
    //多加一行一列，用于设置初始条件
    const int N = A.size() + 1;
    const int M = m + 1;
    vector<vector<int> > result;
    result.resize(N);
//初始化所有位置为0，第一行和第一列都为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) {
//第i个商品在A中对应的索引为i-1: i从1开始
//如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
            if (A[i - 1] > j) {
                result[i][j] = result[i - 1][j];
            } 
            //如果可以装下，分两种情况，装或者不装
//如果不装，则即为(i-1, j)
//如果装，需要腾出放第i个物品大小的空间： j - A[i-1],装入之后的最大价值即为(i - 1, j- A[i-1]) + 第i个商品的价值V[i - 1]
//最后在装与不装中选出最大的价值
            else {
                int newValue = result[i - 1][j - A[i - 1]] + V[i - 1];
                result[i][j] = max(newValue, result[i - 1][j]);
            }
        }
    } 
    //返回装入前N个商品，物品大小为m的最大价值
    return result[N - 1][m];
}

 采用一维数组的写法

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

七、回文串分隔

分割回文串-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次）

        

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool isPal(string& s,int start,int end)
     {
         while(start<end)
         {
             if(s[start]!=s[end])
             {
                 return false;
             }
             ++start;
             --end;
         }
         return true;
    }
    int minCut(string s) {
        // write code here

        int len=s.size();
        if(len==0)
            return 0;
        //判断整体是不是一个回文串
        if(isPal(s,0,len-1))
            return 0;

        vector<int> minCut(len+1);
        //F(i)=i-1
        //5个字符中间最多分割4次
        for(int i=1;i<=len;++i)
            minCut[i]=i-1;
        for(int i=2;i<=len;++i)
        {
            //整体是否为回文串
            if(isPal(s,0,i-1))
            {
                minCut[i]=0;
                continue;
            }
            // j<i&&[j+1,i]是否为回文串
            for(int j=1;j<i;++j)
            {
                if(isPal(s,j,i-1))
                {
                    minCut[i]=min(minCut[i],minCut[j]+1);
                }
            }
            
        }
        return minCut[len];
    }
};

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

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool isPal(string& s,int start,int end)
     {
         while(start<end)
         {
             if(s[start]!=s[end])
             {
                 return false;
             }
             ++start;
             --end;
         }
         return true;
    }
    int minCut(string s) {
        // write code here

        int len=s.size();
        if(len==0)
            return 0;
        if(isPal(s,0,len-1))
            return 0;
        vector<int> minCut(len+1);
        //F(i)=i-1
        for(int i=0;i<=len;++i)
            minCut[i]=i-1;
        for(int i=2;i<=len;++i)
        {
            // j<i&&[j+1,i]是否为回文串
            for(int j=0;j<i;++j)
            {
                if(isPal(s,j,i-1))
                {
                    minCut[i]=min(minCut[i],minCut[j]+1);
                }
            }
            
        }
        return minCut[len];
    }
};

 但是上面的主代码中存在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

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool isPal(string& s,int start,int end)
     {
         while(start<end)
         {
             if(s[start]!=s[end])
             {
                 return false;
             }
             ++start;
             --end;
         }
         return true;
    }
    vector<vector<bool>> getMat(string & s)
    {
        int n=s.size();
        vector<vector<bool>> Mat(n,vector<bool>(n,false));
        for(int i=n-1;i>=0;--i)
        {
            for(int j=i;j<n;++j)
            {
                if(j==i)
                {
                    Mat[i][j]=true;
                }
                else if(j==i+1)
                {
                    Mat[i][j]=s[i]==s[j];
                }
                else
                {
                    Mat[i][j]=(s[i]==s[j])&&(Mat[i+1][j-1]);
                }
            }
        }
        return Mat;
    }
    int minCut(string s) {
        // write code here

        int len=s.size();
        if(len==0)
            return 0;
        if(isPal(s,0,len-1))
            return 0;
        vector<int> minCut(len+1);
        //F(i)=i-1
        vector<vector<bool>> Mat=getMat(s);
        for(int i=0;i<=len;++i)
            minCut[i]=i-1;
        for(int i=2;i<=len;++i)
        {
            // j<i&&[j+1,i]是否为回文串
            for(int j=0;j<i;++j)
            {
                if(Mat[j][i-1])
                {
                    minCut[i]=min(minCut[i],minCut[j]+1);
                }
            }
            
        }
        return minCut[len];
    }
};

八、编辑距离

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

描述

给定两个单词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:删除

class Solution {
public:
    /**
     * 
     * @param word1 string字符串 
     * @param word2 string字符串 
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        // write code here
        int row=word1.size();
        int col=word2.size();

        vector<vector<int>> minD(row+1,vector<int>(col+1));
        //初始化F(1,0):i  F(0,j):j 第一行和第一列
        for(int i=0;i<=col;++i)
        {
            minD[0][i]=i;
        }
        for(int i=1;i<=row;++i)
        {
            minD[i][0]=i;
        }
        for(int i=1;i<=row;++i)
        {
            for(int j=1;j<=col;++j)
            {
                //插入、删除
                //插入和删除的步数中选择一个步数最小的，然后+1
                minD[i][j]=min(minD[i][j-1],minD[i-1][j])+1;
                //替换
                //如果word1的第i个就等于word2的第j个，就不需要替换
                if(word1[i-1]==word2[j-1])
                {
                    //替换是在对角线上
                    minD[i][j]=min(minD[i][j],minD[i-1][j-1]);
                }
                else{
                    //从插入删除和替换中选择一个步数最少的
                    minD[i][j]=min(minD[i][j],minD[i-1][j-1]+1);
                }
            }
            
        }
        return minD[row][col];
    }
};

九、不同子序列

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

描述

给定两个字符串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)

        

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

                F(0,j)=0  (j!=0);

class Solution {
  public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return int整型
     */
    int numDistinct(string S, string T) {
        int s_size = S.size();
        int t_size = T.size();
// S的长度小于T长度，不可能含有与T相同的子串
        if (S.size() < T.size()) return 0;
// T为空串，只有空串与空串相同，S至少有一个子串，它为空串
        if (T.empty()) return 1;
// F(i,j)，初始化所有的值为0
        vector<vector<int> > f(s_size + 1, vector<int>(t_size + 1, 0));
// 空串与空串相同的个数为1
        f[0][0] = 1;
        for (int i = 1; i <= s_size; ++i) {
// F(i,0)初始化
            f[i][0] = 1;
            for (int j = 1; j <= t_size; ++j) {
// S的第i个字符与T的第j个字符相同
                if (S[i - 1] == T[j - 1]) {
                    f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
                } 
                else {
// S的第i个字符与T的第j个字符不相同
// 从S的前i-1个字符中找子串，使子串与T的前j个字符相同
                    f[i][j] = f[i - 1][j];
                }
            }
        } 
        return f[s_size][t_size];
    }
};

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

class Solution {
  public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return int整型
     */
    int numDistinct(string S, string T) {
        if (S.empty())
            return 0;
        if (T.empty())
            return 1;
        int len1 = S.size();
        int len2 = T.size();
        vector<int> numDis(len2 + 1, 0);
        numDis[0] = 1;
        for (int i = 1; i <= len1; ++i) {
            //从后向前更新，因为我们所需要使用的是未更新的值，也就是上一行的值
            for (int j = len2; j > 0; --j) {
                if (S[i - 1] == T[j - 1])
                    numDis[j] = numDis[j - 1] + numDis[j];
            //如果相同的话，本一次更新就等于上一次的数据
            }
        } 
        return numDis[len2];
    }
};

动态规划状态定义：

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

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

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

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

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

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

                首先尝试一维状态，

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

        常见问题的状态：

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

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