c语言（0，0）到（m，n）点的走法

这是一个典型的动态规划问题。假设f(i,j)表示从(0,0)到(i,j)的走法总数，则有如下递推式：

f(i,j) = f(i-1,j) + f(i,j-1)

其中，当i=0或j=0时，f(i,j)=1。这是因为只能向右或向下走一步，所以只有一种走法。

最终的答案即为f(m,n)。

下面是一个简单的C语言实现：

#include <stdio.h>

int main()
{
    int m, n;
    printf("请输入m和n：");
    scanf("%d %d", &m, &n);
    int f[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                f[i][j] = 1;
            } else {
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
    }
    printf("从(0,0)到(%d,%d)的走法总数为：%d\n", m, n, f[m][n]);
    return 0;
}

相关问题

回溯法0-1背包问题c语言

下面是使用回溯法解决0-1背包问题的C语言代码：

#include <stdio.h>

#define MAX_N 100

int n, m; // 物品数量n，背包容量m
int w[MAX_N], v[MAX_N]; // 每个物品的重量w和价值v
int max_v = -1; // 最大价值

void dfs(int i, int weight, int value)
{
    if (i == n) // 所有物品已经考虑完
    {
        if (value > max_v) // 更新最大价值
            max_v = value;
        return;
    }
    if (weight + w[i] <= m) // 如果当前物品可以放入背包
        dfs(i+1, weight+w[i], value+v[i]); // 选择放入当前物品
    dfs(i+1, weight, value); // 不放入当前物品
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &w[i], &v[i]);
    dfs(0, 0, 0); // 从第0个物品开始考虑，当前重量和价值都为0
    printf("%d\n", max_v); // 输出最大价值
    return 0;
}

代码思路：

使用深度优先搜索（DFS）来实现回溯。

每次考虑一个物品，有两种选择：放入背包或不放入背包。如果当前物品可以放入背包，则递归调用dfs(i+1, weight+w[i], value+v[i])；否则递归调用dfs(i+1, weight, value)。当考虑完所有物品后，更新最大价值max_v。

动态规划法解决0-1背包C语言

以下是用动态规划法解决0-1背包问题的C语言代码：

#include <stdio.h>
#define N 1000 // 物品个数的最大值
#define W 1000 // 背包容量的最大值

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m, w[N], v[N], dp[N][W]; // n表示物品个数，m表示背包容量，w表示物品重量，v表示物品价值，dp表示动态规划数组
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j >= w[i]) { // 如果背包容量足够放下第i件物品
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); // 取第i件物品和不取第i件物品中的最大值
            } else { // 如果背包容量不足以放下第i件物品
                dp[i][j] = dp[i - 1][j]; // 不放第i件物品
            }
        }
    }
    printf("%d\n", dp[n][m]); // 输出最大价值
    return 0;
}

这段代码使用二维数组`dp[i][j]`表示在前i个物品中，背包容量为j时的最大价值。通过递推填充`dp`数组，最终得到`dp[n][m]`即为问题的解。