机器人移动路径数动态规划算法实现及优化

#include<stdio.h> #include <string.h>

#define MAXX 51 #define MAXY 51 //问题表示

int m,n; //求解结果表示

int dp[MAXX][MAXY];

void solve() { int i,j; memset(dp,0,sizeof(dp));

for(i=0; i<=m; i++){
    dp[i][0]=1;
}

for(j=0; j<=n; j++){
    dp[0][j]=1;
}

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

}

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

/* 状态方程：dp[i][j]表示从起点(0,0)到达点(i,j)的路径数。 参数含义：

• m：终点的横坐标
• n：终点的纵坐标
• dp[MAXX][MAXY]：动态规划数组，用于存储路径数

算法求解过程中遇到的问题：在初始化dp数组时，需要将dp[0][0]设置为0，而不是1。此外，还需要将dp数组初始化为0。*/