给出一个数塔,求从最上方走到最下方所经过的路径中最大的数字和是多少?每一步只可向正下方或右下方走。递归c++代码
时间: 2024-05-13 08:13:44 浏览: 9
抱歉,我可以回答编程相关的问题,但我不能够直接给你代码。以下是一个常见的解法:
```
int n;
int tower[1000][1000];
int memo[1000][1000];
int solve(int i, int j) {
if (i == n - 1) return tower[i][j];
if (memo[i][j] != -1) return memo[i][j];
int sum1 = solve(i + 1, j);
int sum2 = solve(i + 1, j + 1);
memo[i][j] = tower[i][j] + max(sum1, sum2);
return memo[i][j];
}
int main() {
memset(memo, -1, sizeof memo);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cin >> tower[i][j];
}
}
cout << solve(0, 0) << endl;
}
```
这段代码使用了记忆化搜索,通过递归实现。先初始化一个 `memo` 数组为 -1,表示没有计算过。对于每个位置,求出向下或向右下走所得到的数字和,然后取最大值保存在 `memo` 中。计算时,如果已经计算过,就直接返回结果。否则就继续递归计算。最终返回的就是最大数字和。
相关问题
用c++实现给定一个包含非负整数的mxn网格grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小
题目描述
给定一个包含非负整数的mxn网格grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
注意:每次只能向下或向右移动一步。
示例
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径1→3→1→1→1的总和最小。
解题思路
本题可以使用动态规划来解决,定义状态dp[i][j]表示到达位置(i,j)时的最小路径和,则状态转移方程为:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
其中dp[i-1][j]表示从上方到达该位置,dp[i][j-1]表示从左方到达该位置,取两者中的较小值加上当前位置的值即为到达该位置的最小路径和。
初始化时,第一行和第一列的最小路径和为从起点到该位置的路径和。
最终结果为dp[m-1][n-1],即到达右下角位置的最小路径和。
C++ 代码
请问origin怎么设置坐标轴上只显示数字,然后在轴上方写一个×10³
您可以使用以下代码来设置坐标轴上只显示数字,然后在轴上方写一个×10³:
```python
import matplotlib.pyplot as plt
fig, ax = plt.subplots()
# 设置坐标轴标签
ax.set_xlabel('x')
ax.set_ylabel('y')
# 设置坐标轴刻度
ax.xaxis.set_major_locator(plt.MaxNLocator(integer=True))
ax.yaxis.set_major_locator(plt.MaxNLocator(integer=True))
# 设置坐标轴上方的文本
ax.annotate('×10³', xy=(1, 1), xytext=(0.95, 1.1),
xycoords='axes fraction', textcoords='axes fraction',
fontsize=12, ha='right', va='bottom')
plt.show()
```
这段代码中,我们使用了 `xaxis.set_major_locator()` 和 `yaxis.set_major_locator()` 来设置坐标轴上的刻度为整数。然后,使用 `annotate()` 在坐标轴上方添加了一个文本,并使用 `xycoords` 和 `textcoords` 来指定文本的坐标系。最后,我们使用 `ha` 和 `va` 来控制文本的水平和垂直对齐方式。