机器人移动路径计数：动态规划算法实现

机器人移动路径计数：动态规划算法实现

问题描述：

一个机器人只能向下和向右移动，每次只能移动一步，设计一个算法求它从(0,0)移动到(m,n)有多少条路径。

算法说明：

使用动态规划，定义一个二维数组dp[m][n]，其中dp[i][j]表示从(0,0)移动到(i,j)的路径条数。递推关系为dp[i][j] = dp[i-1][j] + dp[i][j-1]，即从上面或者左边过来的路径数之和。初始状态dp[0][0] = 1，dp[i][0] = 1，dp[0][j] = 1。最终结果为dp[m-1][n-1]。

C语言程序源码：

#include <stdio.h>

int uniquePaths(int m, int n) {
    int dp[m][n];
    for(int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for(int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

int main() {
    int m = 3, n = 7;
    printf("The number of unique paths from (0,0) to (%d,%d) is %d.\n", m-1, n-1, uniquePaths(m, n));
    return 0;
}

运行结果截图：

时间复杂度分析：

DP算法的时间复杂度为O(mn)，空间复杂度也为O(mn)。因为需要遍历整个二维数组dp，所以时间复杂度为O(mn)。空间复杂度为O(mn)是因为需要一个二维数组dp来记录每个子问题的解。