机器人硬币收集.动态规划

Question

机器人硬币收集问题

几个硬币被放置在一个n × m板的细胞中，每个细胞不超过一个硬币。一个机器人，位于板的左上角，需要收集尽可能多的硬币，并将它们带到右下角的单元格。在每一步中，机器人可以将一个单元移动到右边，也可以从当前位置向下移动一个单元。当机器人用硬币访问一个牢房时，它总是捡起那枚硬币。设计了一种算法来找出机器人可以收集的硬币的最大数量，以及它需要遵循的路径。 如果机器人无法访问棋盘上的一些单元，您将如何修改硬币收集问题的动态规划算法？把你的算法应用到下面的板上，在这里，无法访问的单元格用X表示。这个板有多少条最优路径？

我对上面的图像进行了编码，输出结果显示为4，它运行良好。不可访问的单元格标记为-1。然而，我让a[0][1]=1可以访问，我遇到了一个奇怪的问题，它显示初始化后的a[1][0]=3，输出是6而不是5。单元格a[1][0]如何显示为3而不是1？无论我在a[0][1]改变什么，都会在a[1][0]受到影响。怎么会这样呢？我哪里出问题了？

#include <stdio.h>

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

int robot_coin_collect(int m,int n,int a[][n])
{
    int i=1,j=1,k,c[m][n];

    c[0][0]=a[0][0];
    while(a[i][0]!=-1)
    {
        c[i][0]=c[i-1][0]+a[i][0];
        i=i+1;
    }
    for(;i<m;i++)
        c[i][0]=-6;
    while(a[0][j]!=-1)
    {
        c[0][j]=c[0][j-1]+a[0][j];
        j=j+1;
    }
    for(;j<n;j++)
        c[0][j]=-6;

    display(m,n,c);      // after initialising 
    printf("\n\n");

    for(i=1;i<m;i++)
    {
         for(j=1;j<n;j++)
         {
            if(a[i][j]!=-1)
                c[i][j]=max(c[i-1][j],c[i][j-1])+a[i][j];
            else
                c[i][j]=-6;
         }
    } 

    display(m,n,c);      // after the algorithm finishes, result
    return c[m-1][n-1];
}

void display(int m,int n,int c[][n])
{
     int i,j;

     for(i=0;i<m;i++)  
     {   
        for(j=0;j<n;j++)
            printf("%d\t",c[i][j]);
        printf("\n");
    }
}

int main(void) 
{
     int a[5][6]={0,1,0,1,0,0,
                 1,0,0,-1,1,0,
                 0,1,0,-1,1,0,
                 0,0,0,1,0,1,
                 -1,-1,-1,0,1,0};

     printf("%d",robot_coin_collect(5,6,a));
     return 0;
}

Answer 1

问题是，当第一行或第一列中没有任何-1时，您的代码可以修改内存单元格，该单元格在数组边界之外。

这很奇怪，为什么没有运行时错误，您可以看到this link和this。

在时间条件中添加界限限制：

while(i<m && a[i][0]!=-1)
{
    c[i][0]=c[i-1][0]+a[i][0];
    i=i+1;
}

和

while(j<n && a[0][j]!=-1)
{
    c[0][j]=c[0][j-1]+a[0][j];
    j=j+1;
}

Answer 2

int CoinCollecting(int c[][], int M[][],int i,int j){
    int Max(int a,int b) 
    {
        return a>b?a:b;
    }
    if(i==0 || j==0)
    {
        M[i][j]=0;
        return 0;
    }
    if(m[i-1][j]<0)
    {
        M[i-1][j]=CoinCollecting(c[][],M[][],i-1,j);
    }

if(m[i][j-1]<0)
{
    M[i][j-1]=CoinCollecting(c[][],M[][],i,j-1);
}

M[i][j]=Max(M[i-1][j],M[i][j-1]+c[i][j]);
return M[i][j]
}