动态规划

$ n^2 $

Alchemist (dp 填表练习地址)

1. 判断子序列

一个比较直观的思路是双指针，但是数据量大了就不行，上 DP

为便于分清，设要验证的子序列名为sub ，主序列为sequence

对于前缀sub[ i ],若sub[ i ]是sequence[ j ]的子序列，则sub[ i ] 一定是sequence 的子序列

所以可以设二维dp方程 dp [ m+1] [ n+1] 行代表sub 列代表sequence

再初始化空串的状态，从小往大转移即可

状态方程如下： $$ dp[i][j]= \begin{cases} & true & if \quad dp[i-1][j-1]=true \ && \ sub[i-1]==sequence[j-1]\ & false & else& \end{cases} $$

代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
         int m = s.length(), n = t.length();
         vector<vector<bool> > dp(m+1,vector<bool> (n+1,true));
         for(int i = 1; i < m+1; i++) dp[i][0] = false;
         //初始化dp
         for(int i = 1; i < m+1; i++){
             for(int j = 1; j < n+1; j++){
                 if(s[i-1] == t[j-1] && dp[i-1][j-1]){
                    dp[i][j] = true;
                    break;
                 }else{
                    dp[i][j] = false; 
                 }
             }
         }
         return dp[m][n];
    }
};

2. 除数博弈

这个博弈有个结论，但我们还是得用dp求解.

dp 思路如下：

对于1 2 的状态我们可以很容易推出：1 为先手false ，2 为先手 true

对于下一个状态 i ，我们依次枚举 [1 ，i -1 ] 如果有满足的因子 j ，且替换时可以把必败态转给对手，那么dp[ i ] = true

状态方程如下： $$ dp[i] = ( , !dp[i-j] , && , i % j == 0 \ ), ? ,true : false $$ 代码

class Solution {
public:
    bool divisorGame(int n) {
        vector<bool> dp(n+1,false);
        dp[1] = false;
        dp[2] = true;
        for(int i = 3; i <= n; i++)
            for(int j = 1; j < i; j++)
                if(i%j == 0 && dp[i-j] == false){
                    dp[i] = true;
                    break;
                }
        return dp[n];
    }
};

3. 三步问题

思路如下：

零阶：可以看成不动，那么有一种 1

一阶：只有一种 1

二阶：有两种 1+1 和 2

三阶：有 1+1+1 和 2+1 和 3

四阶：四阶可以由一阶或二阶或三阶上来

那么四阶的总数为 1 + 2 + 4 = 7

......

不难想到

第n阶 = 第n-1阶 + 第n-2阶 + 第n-3 阶

状态转移方程如下: $$ dp[i] = dp[i-1] + dp[i-2] + dp[i-3] $$ 另外还要取模关于取模公式如下： $$ (a+b) % p = (a % p + b % p) % p $$ 代码

class Solution {
public:
    static const long mod =1000000007;
    static const int N = 1000010;
    int dp[N];
    int waysToStep(int n) { 
        dp[0] = 1,dp[1] = 1, dp[2] = 2,dp[3] =4;
        for(int i = 4; i <= n; i++){
            dp[i] = (dp[i-1] % mod + dp[i-2] % mod + dp[i-3] % mod ) % mod;
        }
        return dp[n];
    }
};

4. 连续子数组最大和

思路如下：

这道题，很容易想到一个前缀和的方法，但是容易超时。

令 dp[i] 表示以i结尾的连续子数组的最大和，对于dp[i+1] ,显然有

dp[i+1] = max(dp[i] + nums[i+1] , nums[i+1])

即dp[i] = max(dp[i-1] + nums[i] , nums[i])

合并起来就是

dp[i+1] = max(max(dp[i-1] + nums[i] , nums[i]) + nums[i+1], nums[i+1])

其中dp[0] = nums[0]

所以我们可以在枚举每个nums[i]结尾的子数组时，依次计算最大和，最后便可以得到答案了

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        
        dp[0] = nums[0];
        if(n == 1) return dp[0];

        dp[1] = max(dp[0]+nums[1], nums[1]);
        if(n == 2) return max(dp[1],dp[0]);

        for(int i = 2; i < n; i++){
            dp[i] =  max( dp[i-1] + nums[i] , nums[i]);
        }
        return *max_element(dp.begin(),dp.end());
    }
};

可以发现最后我们还要求一下最大的dp[i] 所以简化一下写法，就是下面这样啦

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0], pre = 0;
        for(auto && n : nums){
            pre = max(pre+n,n);
            ans = max(pre,ans);
        }
        return ans;
    }
};

XR-stb/DP-

动态规划

1. 判断子序列

2. 除数博弈

3. 三步问题

4. 连续子数组最大和