动态规划 不同路径 II用c语言实现

以下是动态规划不同路径 II的C语言实现：

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int m = obstacleGridSize, n = obstacleGridColSize[0];
    int dp[m][n];
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<m; i++){
        if(obstacleGrid[i][0] == 1) break;
        dp[i][0] = 1;
    }
    for(int j=0; j<n; j++){
        if(obstacleGrid[0][j] == 1) break;
        dp[0][j] = 1;
    }
    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            if(obstacleGrid[i][j] == 1) continue;
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

希望对您有所帮助！

相关问题

动态规划的车辆路径规划c语言代码

动态规划是一种常用的优化方法，用于解决具有重叠子问题和最优子结构性质的问题。车辆路径规划是其中一个应用场景，可以通过动态规划来求解最优路径。

以下是一个简单的动态规划车辆路径规划的C语言代码示例：

#include <stdio.h>

#define MAX_SIZE 100

int min(int a, int b) {
    return (a < b) ? a : b;
}

int vehicleRouting(int cost[MAX_SIZE][MAX_SIZE], int n) {
    int dp[MAX_SIZE];
    dp[0] = 0;

    for (int i = 1; i < n; i++) {
        dp[i] = cost[0][i];
        for (int j = 1; j < i; j++) {
            dp[i] = min(dp[i], dp[j] + cost[j][i]);
        }
    }

    return dp[n-1];
}

int main() {
    int n;
    printf("请输入节点数量：");
    scanf("%d", &n);

    int cost[MAX_SIZE][MAX_SIZE];    printf("请输入节点之间的距离矩阵：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &cost[i][j]);
        }
    }

    int result = vehicleRouting(cost, n);
    printf("最短路径长度为：%d\n", result);

    return 0;
}

这段代码实现了一个简单的车辆路径规划问题，通过输入节点数量和节点之间的距离矩阵，使用动态规划算法求解最短路径长度。其中，`cost`数组表示节点之间的距离，`dp`数组用于保存中间计算结果。

动态规划最短路径问题c语言

动态规划最短路径问题是指在一个有向图中，从起点到终点有多条路径，每条路径都有一个权值，求其中权值最小的路径。下面是一个使用C语言实现的动态规划最短路径问题的例子：

#include <stdio.h>
#include <limits.h>

#define V 6

int minDistance(int dist[], bool sptSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void printSolution(int dist[])
{
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src)
{
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);

        sptSet[u] = true;

        for (int v = 0; v < V; v++)

            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist);
}

int main()
{
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0 },
                        { 4, 0, 8, 0, 0, 0 },
                        { 0, 8, 0, 7, 0, 4 },
                        { 0, 0, 7, 0, 9, 14 },
                        { 0, 0, 0, 9, 0, 10 },
                        { 0, 0, 4, 14, 10, 0 } };

    dijkstra(graph, 0);

    return 0;
}