&x = dp[k][i1][i2];
时间: 2024-06-02 10:05:57 浏览: 26
&x = dp[k][i1][i2]; 这是一个指针引用的语法,表示取 dp[k][i1][i2] 的地址并将其赋值给 x。这样做的目的是为了让变量 x 和 dp[k][i1][i2] 指向同一块内存地址,即它们是同一个变量的两个名字。这样在对 x 进行修改时,dp[k][i1][i2] 的值也会同时改变。这种指针引用的方式常常用在动态规划等需要大量数组操作的算法中,可以避免不必要的数组访问操作,提高程序效率。
相关问题
for(int i = 1; i <= len; i++) { for(int j = 0; j < 10; j++) { for(int k = 0; k < 10; k++) { if(j != 4 && (j != 6 || k != 2)) dp[i][j] += dp[i - 1][k]; } } } 上面这段代码和下面这段代码为什么不等价呢,第一段代码如何修改才能和第二段代码等价呢: for(int i = 1; i <= len; i++) { for(int j = 0; j < 10; j++) { for(int k = 0; k < 10; k++) { if(j == 4) continue; // 排除数字 4 else if(j == 6 && k == 2) continue; // 排除62 dp[i][j] += dp[i - 1][k]; } } }
这两段代码的区别在于条件判断的逻辑。
第一段代码中,我们使用了逻辑运算符来判断条件。具体来说,我们判断 j 是否不等于 4,并且判断 j 是否不等于 6 或者 k 是否不等于 2。只有当这两个条件都满足时,才会执行 dp[i][j] += dp[i - 1][k] 的操作。
第二段代码中,我们使用了连续的条件判断语句。首先,我们判断 j 是否等于 4,如果是,则跳过本次循环,继续下一次循环。否则,我们继续判断 j 是否等于 6 并且 k 是否等于 2,如果是,则也跳过本次循环,继续下一次循环。在没有跳过的情况下,才会执行 dp[i][j] += dp[i - 1][k] 的操作。
为了使第一段代码和第二段代码等价,可以对第一段代码进行修改如下:
```cpp
for(int i = 1; i <= len; i++) {
for(int j = 0; j < 10; j++) {
for(int k = 0; k < 10; k++) {
if(j == 4 || (j == 6 && k == 2)) continue;
dp[i][j] += dp[i - 1][k];
}
}
}
```
通过将条件判断的逻辑取反,将 `!=` 改为 `==`,再使用 `continue` 来跳过不满足条件的情况,即可使第一段代码和第二段代码等价。
这一段代码为什么不能求解出[0~n不包含4的数的个数呢: int dfs(int len, bool ismax) { // ismax为数位上界变量 if(len == 0) return 1; if(!ismax && dp[len] != -1) return dp[len]; int ans = 0, maxx = ismax ? digit[len] : 9; for(int i = 0; i <= len; i++) { if(i == 4) continue; //if(pre == 6 && i == 2) continue; ans += dfs(len - 1, ismax && i == maxx); } if(!ismax) dp[len] = ans; return ans; }
这段代码是一个递归函数 `dfs`,用于计算不包含数字 4 的数的个数。
代码中的 `dfs` 函数接受两个参数:`len` 表示当前数位的位置,`ismax` 表示当前数位是否达到上界。
首先,递归终止条件是当 `len` 等于 0 时,表示已经处理完所有数位,可以返回 1。
然后,在递归过程中,首先判断是否需要使用已经计算过的结果。如果 `ismax` 为假且 `dp[len]` 不等于 -1,则说明之前已经计算过当前数位的结果,可以直接返回结果。
接下来,定义变量 `ans` 用于记录满足条件的数字个数,以及变量 `maxx` 表示当前数位的上界。如果 `ismax` 为真,则 `maxx` 等于当前数位 `digit[len]`,否则 `maxx` 等于 9。
然后,使用循环从 0 到 `len` 遍历所有可能的取值 `i`。在每次循环中,判断如果 `i` 等于 4,则跳过当前循环,排除数字 4。然后,递归调用 `dfs` 函数,传入 `len - 1` 和 `ismax && i == maxx` 作为参数,并将返回的结果累加到 `ans` 中。
最后,如果 `ismax` 为假,则将结果 `ans` 存入 `dp[len]`,以备之后的计算使用,并返回 `ans`。
这段代码通过递归的方式,不断地将问题规模缩小,直到达到终止条件。在每一层递归中,通过判断条件来决定是否进一步递归,并将结果累加到最终的答案中。在需要时,利用 `dp` 数组保存已经计算过的结果,以避免重复计算,提高效率。
要计算 [0~n) 区间内不包含数字 4 的数的个数,可以调用 `dfs(n, true)`。其中,`n` 是区间的上界,`true` 表示达到上界。
注意,这段代码中有一处注释掉的判断语句 `//if(pre == 6 && i == 2) continue;`。如果需要排除以 62 开头的数字,可以取消注释该语句,并在每次递归调用 `dfs` 时传入 `i` 作为前一位数字的参数。