上楼梯题解

上楼梯问题是一个经典的递归问题。问题描述如下：一个人要上 n 级台阶，每次只能上 1 级或 2 级，问有多少种不同的方法可以走完这 n 级台阶。

使用递归算法来解决上楼梯问题，可以写出如下的递归函数：

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

在这个递归函数中，当 n 等于 1 时，返回 1；当 n 等于 2 时，返回 2；否则，返回上一级和上两级的方法之和。这个递归函数可以计算任意一个台阶数的不同上楼梯方法数。

例如，当 n 等于 4 时，这个递归函数的调用过程如下：

climbStairs(4)
= climbStairs(3) + climbStairs(2)
= (climbStairs(2) + climbStairs(1)) + 2
= 2 + 1 + 2
= 5

因此，当 n 等于 4 时，有 5 种不同的上楼梯方法。

需要注意的是，递归算法的时间复杂度可能会很高，因为有很多重复计算。例如，当 n 等于 5 时，climbStairs(3) 会被计算两次。因此，为了避免重复计算，可以使用动态规划等方法来优化递归算法。

相关问题

树上选点蓝桥Java题解

树上选点是蓝桥杯Java题目中的一种类型，通常需要在给定的树结构中选择一个或多个节点作为目标节点，并进行相应的操作。下面是一个简单的树上选点蓝桥Java题解的示例：

题目描述：
给定一棵有N个节点的树，每个节点上都有一个非负整数值。现在需要选择一些节点，使得选择的节点的值之和最大，且所选节点不能相邻（即选了一个节点，则其父节点和子节点都不能选）。请编写一个程序，计算出最大的节点值之和。

解题思路：
这是一个典型的动态规划问题。我们可以定义一个数组dp，其中dp[i]表示以第i个节点为根节点的子树中所选节点的最大值之和。对于每个节点i，有两种情况：
1. 选择节点i：则其子节点都不能选，所以dp[i] = val[i] + dp[grandchild1] + dp[grandchild2] + ...
2. 不选择节点i：则其子节点可以选择或不选择，所以dp[i] = max(dp[child1], dp[child2], ...)

根据以上思路，我们可以使用递归或者迭代的方式来计算dp数组。最终，所求的最大值即为dp，其中1表示根节点。

代码示例：

public class TreeSelectPoint {
    public static void main(String[] args) {
        int[] values = {0, 1, 2, 3, 4, 5}; // 节点值数组，下标从1开始
        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}; // 树的边关系数组

        int n = values.length - 1; // 节点个数
        int[] dp = new int[n + 1]; // 动态规划数组

        // 构建树的邻接表
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adjacencyList.get(u).add(v);
            adjacencyList.get(v).add(u);
        }

        dfs(1, -1, values, adjacencyList, dp); // 从根节点开始进行深度优先搜索

        System.out.println(dp[1]); // 输出最大节点值之和
    }

    private static void dfs(int cur, int parent, int[] values, List<List<Integer>> adjacencyList, int[] dp) {
        dp[cur] = values[cur]; // 初始化当前节点的dp值为节点值

        for (int child : adjacencyList.get(cur)) {
            if (child != parent) { // 避免重复访问父节点
                dfs(child, cur, values, adjacencyList, dp);
                dp[cur] += dp[child]; // 更新当前节点的dp值
            }
        }
    }
}

题解

这道题是一道典型的费用限制最短路题目，可以使用 Dijkstra 算法或者 SPFA 算法来解决。

具体思路如下：

1. 首先，我们需要读入输入数据。输入数据中包含了道路的数量、起点和终点，以及每条道路的起点、终点、长度和限制费用。

2. 接着，我们需要使用邻接表或邻接矩阵来存储图的信息。对于每条道路，我们可以将其起点和终点作为一个有向边的起点和终点，长度作为边权，限制费用作为边权的上界。

3. 然后，我们可以使用 Dijkstra 算法或 SPFA 算法求解从起点到终点的最短路径。在这个过程中，我们需要记录到每个点的最小费用和最小长度，以及更新每条边的最小费用和最小长度。

4. 最后，我们输出从起点到终点的最短路径长度即可。

需要注意的是，在使用 Dijkstra 算法或 SPFA 算法时，需要对每个点的最小费用和最小长度进行松弛操作。具体来说，当我们从一个点 u 经过一条边 (u,v) 到达另一个点 v 时，如果新的费用和长度比原来的小，则需要更新到达 v 的最小费用和最小长度，并将 v 加入到优先队列（Dijkstra 算法）或队列（SPFA 算法）中。

此外，还需要注意处理边权为 0 或负数的情况，以及处理无法到达终点的情况。

代码实现可以参考以下样例代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1005, MAXM = 20005, INF = 0x3f3f3f3f;

int n, m, s, t, cnt;
int head[MAXN], dis[MAXN], vis[MAXN];

struct Edge {
    int v, w, c, nxt;
} e[MAXM];

void addEdge(int u, int v, int w, int c) {
    e[++cnt].v = v, e[cnt].w = w, e[cnt].c = c, e[cnt].nxt = head[u], head[u] = cnt;
}

void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w, c = e[i].c;
            if (dis[u] + w < dis[v] && c >= dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w, c;
        scanf("%d %d %d %d", &u, &v, &w, &c);
        addEdge(u, v, w, c);
        addEdge(v, u, w, c);
    }
    dijkstra();
    if (dis[t] == INF)
        printf("-1\n");
    else
        printf("%d\n", dis[t]);
    return 0;
}