機器人硬幣收集 - 動態規劃

Question

機器人硬幣收集問題

若干硬幣被放置在n × m板的細胞，無細胞每超過 一個硬幣。位於 紙板左上角的機器人需要收集儘可能多的硬幣，並將 帶到右下角​​的單元格。在每一步中，機器人都可以將一個單元移動到右側，也可以從當前位置向下移動一個單元。當機器人用一枚硬幣來訪問一個單元格時，它總是拿起那枚硬幣。 設計一種算法來查找機器人可以收集的最大硬幣數量以及它需要遵循的路徑。

如果電路板上的某些單元不可用於 機器人，您將如何修改硬幣的動態編程算法 收集問題？將你的算法應用到下面的板上，其中不可訪問的 單元由X顯示。這塊 板有多少條最佳路徑？

我編碼上述圖像，並且它的工作原理以及輸出顯示4.不可訪問單元被標記爲-1。但是，我使a[0][1]=1可訪問，我得到一個奇怪的問題，其中顯示a[1][0]=3初始化後，輸出是6而不是5.如何顯示單元格a[1][0]而不是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的第一行或第一列

中爲什麼沒有這個奇怪運行時錯誤，你可以看到在while條件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] 
}