1 补全动态规划算法程序，并调试运行。 【问题描述】一个机器人只能向下和向右移动，每次只能移动一步，设计一个算法求它从 (0， 0)移动到(m，n)有多少条路径。 【求解思路】设从(0，0)移动到(i，j)的路径条数为 dp[i][j]，由于机器人只能向下和向右移动，对应的状 态转移方程如下: dp[0][j]=1 dp[i][0]=1 dp[i][j]=dp[i][j-1]+dp[i-1][j] i、j>0 最后结果是 dp[m][n]。 补全下面的程序并调试运行。 #include<stdio.h> #include <string.h> #define MAXX 51 #define MAXY 51 //问题表示 int m,n; //求解结果表示 int dp[MAXX][MAXY]; void solve() { int i,j; dp[0][0]=0; memset(dp,0,sizeof(dp)); for (i=1;i<=m;i++) ① for (j=1;j<=n;j++) ② ③ ④ ⑤ } void main() { m=5,n=3; solve(); printf("%d\n",dp[m][n]); }

补全后的程序如下：

#include<stdio.h>
#include<string.h>
#define MAXX 51
#define MAXY 51

// 问题表示
int m, n;

// 求解结果表示
int dp[MAXX][MAXY];

void solve() {
    int i, j;

    // 初始化
    dp[0][0] = 1;
    memset(dp, 0, sizeof(dp));

    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
}

int main() {
    m = 5, n = 3;
    solve();
    printf("%d\n", dp[m][n]);
    return 0;
}

运行结果为 15，即从 (0,0) 移动到 (5,3) 共有 15 条不同的路径。