"dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];" 这是什么意思？

Question

谁能帮我解决这个疑问：

bool isInterleave(string s1, string s2, string s3) {
        int n1 = (int)s1.size(), n2 = (int)s2.size(), n3 = (int)s3.size(); 
        if(n1 + n2 != n3) return false;
        
        vector<vector<bool>> dp(n1 + 1, vector<bool>(n2 + 1, false));
        dp[0][0] = true;
        
        for(int i2 = 1; i2 <= n2; i2++) dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];
        for(int i1 = 1; i1 <= n1; i1++) dp[i1][0] = dp[i1 - 1][0] && s1[i1 - 1] == s3[i1 - 1];

        for(int i1 = 1; i1 <= n1; i1++){
            for(int i2 = 1; i2 <= n2; i2++){
                dp[i1][i2] = (dp[i1 - 1][i2] && s1[i1 - 1] == s3[i1 + i2 - 1]) || (dp[i1][i2 - 1] && s2[i2 - 1] == s3[i1 + i2 - 1]);
            }
        }
        
        return dp[n1][n2];  
    }

我想知道下面一行的意思：

for(int i2 = 1; i2 <= n2; i2++) dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];

它是在执行某些条件检查还是什么？

我在阅读一些与动态规划相关的问题时得到了这个说法。

Answer 1

它是测试两个条件并分配逻辑结果的简洁形式。

dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1]

dp[0][i2] = ((dp[0][i2 - 1] != false) && (s2[i2 - 1] == s3[i2 - 1]))) ? true : false;

if ((dp[0][i2 - 1] != false) && (s2[i2 - 1] == s3[i2 - 1])))
{
  dp[0][i2] = true;
}
else
{
  dp[0][i2] = false;
}

Answer 2

for(int i2 = 1; i2 <= n2; i2++){
    dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];
}

上面的 for 循环在范围 [1, n2] 上迭代，即 1 到 n2，包括两者。

dp 是一个存储布尔值的二维数组，其中布尔值是根据 dp 数组同一行的前一列值计算的，即这里的第 0 行，并且还检查字符串 s2 和 s3 在索引 i2-1.

处具有相同的字符

让我举个例子来说明这一点：-

假设你的 dp 数组如下：-

-----------------------------
| True | True | False| True |
| True | False| True | True |
| False| True | False| True |
-----------------------------

它有 3 行和 4 列。

另外让我们考虑如下两个字符串：-

s2 = "ROOT" s3 = "鼹鼠"

由于代码仅迭代第 0 行，因此让我们将您的 i2 视为 2。

因此，如您所见，dp[0][i2] = "False" 和 dp[0][i2-1] = "True" i2 为 2

并且当您比较字符串 s1 和 s2 中索引 i2-1 的字符时，即 1，因此 s1[i2-1] == s2[i2-1] 为真，因为两个位置的字符相同：s1[i2-1] = s2[i2-1] = 'O'

所以结合条件 dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1] 会给你 True && True 这是 True 并且代码将 dp[0][i2] 的值更新为 True

Answer 3

for(int i2 = 1; i2 <= n2; i2++){ 
     dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];
}

每个表达式 return 都是一个值，表达式 s2[i2 - 1] == s3[i2 - 1] 将得到 1 或 0。当使用 && 运算符时，它会将所有内容转换为布尔值。每个非零值都被视为 1，每个零值都被视为 0。因此，像 (3 && 6) 这样的表达式将 return 1.

dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1] 将以相同的方式计算。 == 比 && 有更多的存在，因此将首先对其进行评估。因此 s2[i2 - 1] == s3[i2 - 1] 将 return 一个布尔值，然后用 dp[0][i2 - 1] && x 计算该值，其中 x 是 return 从 s2[i2 - 1] == s3[i2 - 1] 编辑的值。它最终将评估为一个布尔值，该值将存储在 dp[0][i2].

中

"dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];" 这是什么意思？

What does "dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];" this mean?

c++

dynamic-programming