第四步三个二维 DP

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

网格路径和带障碍的网格路径已给出，补全编辑距离，输出「3 行 4 列/(1,1) 有石头/horse 变 ros」三个答案。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第三步两个区间 DP 交付独立设计 DP 状态 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Item = pair<int, int>;   // (重量, 价值)

const vector<Item> ITEMS = {{3, 8}, {4, 9}, {5, 11}};
const vector<vector<int>> GRID = {{0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 0}};

long long paths(int m, int n) {
    vector<vector<long long>> dp(m, vector<long long>(n, 1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
    return dp[m - 1][n - 1];
}

long long paths_ob(const vector<vector<int>>& g) {
    int m = g.size(), n = g[0].size();
    vector<vector<long long>> dp(m, vector<long long>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 1) continue;
            if (i == 0 && j == 0) {
                dp[i][j] = 1;
                continue;
            }
            long long up = i > 0 ? dp[i - 1][j] : 0;
            long long left = j > 0 ? dp[i][j - 1] : 0;
            dp[i][j] = up + left;
        }
    }
    return dp[m - 1][n - 1];
}

int edit(const string& a, const string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    // TODO: 先把第一列填成 0,1,2,…，第一行填成 0,1,2,…（和空串比要几步）
    // TODO: 再逐格填：字符相同取 dp[i-1][j-1]；否则 1 + min(左上, 上, 左)
    return dp[m][n];
}

int main() {
    cout << paths(3, 4) << "/" << paths_ob(GRID) << "/" << edit("horse", "ros") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

第四步三个二维 DP

更多题目

全部评论