摆花

暴力搜索

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000 + 7;
int n, m, ans;
int a[105];
// 当前考虑第now种话摆几盆，之前已经摆了sum种花
void dfs(int now, int sum)
{
    if (sum == m)
    {
        ans++;
        ans %= MOD;
        return;
    }
    if (now > n)
        return;
    // 考虑当前这种花摆几盆
    for (int i = 0; i <= min(a[now], m - sum); i++)
        dfs(now + 1, sum + i);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    ans = 0;
    dfs(1, 0);

    cout << ans << "\n";
    return 0;
}

三重循环

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000 + 7;
int n, m, ans;
int a[105];
int dp[105][105]; // dp[i][j]: 前i种花摆j盆的方案数
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0, sizeof(dp)); // 0种方案表示无解
    // 前0种花摆0盆，有什么都不摆这种方案，前0种花摆其他的盆数都是无解的
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = 1; // 什么都不摆也是一种方案
        for (int j = 1; j <= m; j++)
        {
            // 决策：考虑第i种花摆几盆（k盆）
            for (int k = 0; k <= min(a[i], j); k++)
            {
                // 第 i 种花摆了 k 盆时，需要前 i-1 种花摆 j-k 盆
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
            }
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}

前缀和优化

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000 + 7;
int n, m, ans;
int a[105];
int dp[105][105];  // dp[i][j]: 前i种花摆j盆的方案数
int sum[105][105]; // sum[i][j]: dp[i][0]~dp[i][j] 之和
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0, sizeof(dp)); // 0种方案表示无解
    // 前0种花摆0盆，有什么都不摆这种方案，前0种花摆其他的盆数都是无解的
    dp[0][0] = 1;
    for (int i = 0; i <= m; i++)
        sum[0][i] = 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = 1; // 什么都不摆也是一种方案
        for (int j = 1; j <= m; j++)
        {
            // 决策：考虑第i种花摆几盆（k盆）
            int L = j - min(a[i], j);
            int R = j - 0;
            // dp[i][j] = sum(dp[i-1][L] ...... dp[i-1][R])
            if (L == 0)
                dp[i][j] = sum[i - 1][R];
            else
                dp[i][j] = sum[i - 1][R] - sum[i - 1][L - 1];
            dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
        }
        // 处理dp第i行的前缀和
        sum[i][0] = dp[i][0];
        for (int j = 1; j <= m; j++)
            sum[i][j] = (sum[i][j - 1] + dp[i][j]) % MOD;
    }
    cout << dp[n][m] << "\n";
    return 0;
}

编辑距离

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1, s2;
int dp[2005][2005];
int n, m;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s1 >> s2;
    n = s1.length();
    m = s2.length();
    for (int i = 1; i <= max(n, m); i++)
        dp[i][0] = dp[0][i] = i;
    //s1的前i个
    for (int i = 1; i <= n; i++)
        //s2的前j个
        for (int j = 1; j <= m; j++)
            //比较s1的第i个与s2的第j个
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min(dp[i - 1][j - 1],
                                   min(dp[i - 1][j], dp[i][j - 1]));
    cout << dp[n][m] << endl;
    return 0;
}

大师

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int BASE = 20000 + 5;
int n;
int a[1005];
// dp[i][j]：以 a[i] 结尾，公差为 j 的子序列数量
// 差在 -20000~20000 通过 +BASE 变换到了 -20000+BASE~20000+BASE 即 5~40005
int dp[1005][40000 + 10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 记录答案
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans++;                           // a[i] 自己这种方案记上
        for (int j = i - 1; j >= 1; j--) // 考虑前一个电塔是哪一个
        {
            // 如果接在 a[j] 后面构成一个子序列，公差就是 d=a[i]-a[j]
            int d = a[i] - a[j] + BASE;
            dp[i][d] = (dp[i][d] + (dp[j][d] + 1)) % MOD;
            ans = (ans + (dp[j][d] + 1)) % MOD;
        }
    }
    cout << ans << "\n";
    return 0;
}