codeforces George and Job

/*
    題意：給一個長度為n的序列， 從中選擇長度為m的k個區間（任意兩個區間不會有公共部分）
    使得所選擇的區間的和最大！
    思路：這是一種很常見的dp
    
    dp[i][j] 表示的是前 i 個數選擇 j 個 長度為m區間的最大和！ 
    s[i]記錄的是前 i 個數字的和！ 
    dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] );
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5005
using namespace std;
typedef long long ll;

ll dp[N][N];
ll s[N];

int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &s[i]);
        s[i] += s[i-1];
    }
    
    for(int j = 1; j <= k; ++j)
        for(int i = j*m; i <= n; ++i)
           dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] );
           
    printf("%lld\n", dp[n][k]);
    
    return 0; 
}

?

附一個經典的dp！

題意：
給定2個字符串a, b，求b的子序列在a中出現的次數。要求可以是不連續的，但是b在a中的順序必須和b以前的一致。
思路：
dp[i][j]表示：b的前j個字符在a的前i個字符中出現的次數。
似乎這種表示方法司空見慣，但是一開始我還真沒能搞懂如何去遞推。事情的真相是：
如果a[i] == b[j]則 dp[i][j] = dp[i-1][j] + dp[i-1][j-1];

如果a[i] != b[j]則 dp[i][j] = dp[i-1][j];

?