algorithm - 机器人收币-动态规划

Question

机器人硬币收集问题

Several coins are placed in cells of an n × m board, no more than one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it always picks up that coin. Design an algorithm to find the maximum number of coins the robot can collect and a path it needs to follow to do this.

How would you modify the dynamic programming algorithm for the coin- collecting problem if some cells on the board are inaccessible for the robot? Apply your algorithm to the board below, where the inaccessible cells are shown by X’s. How many optimal paths are there for this board?

我为上图编码，它运行良好，输出显示 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条件中添加限制:

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;
}