請問各位大大：

最近有個程式作業，利用動態規劃的觀念，下面有個矩陣，找一條路徑，起點為左上角，終點為右下角，
，每經過一個位置就累加上面的數值，計算最後到終點經過的值最小？
(要用recurisuve方式完成)，請問有善心人士可以幫我解答嗎？？？
非常感謝你唷︿︿(另外我是用BCB的環境)

此為25*25的矩陣，以空白間隔～

58 35 39 74 33 50 46 44 56 58 37 50 44 43 68 41 22 42 77 69 32 37 51 53 29
45 55 46 27 12 28 63 71 44 39 56 64 29 29 36 60 89 74 44 78 45 53 41 54 52
57 51 73 76 63 32 47 63 46 39 24 46 52 31 48 39 14 69 55 51 60 58 56 42 30
67 30 75 62 27 43 50 51 36 49 53 47 62 31 64 36 56 88 51 46 39 69 52 58 76
76 53 47 85 43 50 43 20 57 16 26 47 67 50 57 33 50 40 49 60 37 84 75 32 24
83 64 87 57 47 85 17 45 34 43 44 41 28 59 60 81 17 64 58 66 66 20 50 29 21
41 56 22 46 62 44 27 60 46 26 82 34 50 40 43 36 62 65 39 59 73 77 74 62 52
76 68 36 60 57 32 26 64 54 57 71 73 43 26 84 45 27 46 38 61 27 55 76 55 31
34 69 47 29 41 73 34 77 21 44 40 55 69 30 59 66 6 53 68 27 50 65 53 42 57
79 34 47 44 48 41 26 38 59 52 59 40 45 68 65 49 59 69 48 63 22 44 54 54 64
30 50 26 45 34 54 50 57 42 79 38 76 53 42 68 37 24 74 63 60 49 80 28 66 40
50 36 43 59 56 50 71 51 70 73 61 56 58 27 54 37 50 35 64 46 66 77 25 65 30
46 64 67 66 78 63 53 20 24 44 71 55 37 71 62 81 42 70 73 80 64 43 39 52 33
45 22 58 47 57 67 60 33 56 30 33 63 42 58 52 52 48 61 48 47 71 68 66 52 67
43 43 31 44 36 44 29 47 76 45 31 68 70 50 23 63 44 45 25 46 77 71 44 43 65
28 36 42 31 21 81 55 54 27 35 48 62 42 34 35 57 48 64 39 76 16 7 43 71 35
48 53 58 57 61 38 51 53 55 55 44 52 37 70 47 36 36 80 74 22 43 80 29 9 56
49 56 33 76 40 44 73 30 24 30 61 57 36 53 48 58 47 52 42 25 63 29 42 50 64
54 33 33 66 58 66 56 37 45 21 74 34 23 42 64 38 77 38 77 46 63 36 80 67 55
37 62 62 26 41 38 23 65 49 71 81 55 71 50 23 61 73 61 48 62 66 32 57 77 39
54 54 62 57 58 39 69 31 55 33 41 52 25 76 54 14 57 53 41 9 77 42 32 37 28
65 83 66 19 41 52 59 49 55 49 59 73 44 39 31 37 49 39 49 40 17 46 65 66 55
45 61 32 41 77 20 67 39 35 58 33 49 32 67 41 41 27 54 53 63 65 50 65 35 45
50 38 37 48 74 20 33 59 61 34 56 47 46 73 49 33 59 60 70 39 78 12 53 21 55
34 76 63 64 65 62 39 52 56 34 59 56 24 74 31 50 37 72 38 55 62 40 69 42 30

附加檔案：474a839c486ec_height_1.txt

編輯記錄

為何不每一條路線都去走看看  最後排序找出最短
反正都是電腦在走

但是要怎麼設計程式，將每一條路都走走看呢？作業還有個要求，不能倒退只能往前或向下走！
請幫我想想該怎麼處理呢？？
謝謝你唷


===================引 用 johnpage 文 章===================
為何不每一條路線都去走看看 最後排序找出最短
反正都是電腦在走

編輯記錄

跑完說一下，將 x_array_max y_arrya_max 改成 25 就是你要的結果。

我run 18 *18 要 C(34,17) = 2333606220 次 約 140sec

run 25*25 要c (48,24)= 32247603683100b次，換算一下，約要 22天。

跑完要說一聲


[code cpp]
#include
const int a[25][25]={
{58,35,39,74,33,50,46,44,56,58,37,50,44,43,68,41,22,42,77,69,32,37,51,53,29},
{45,55,46,27,12,28,63,71,44,39,56,64,29,29,36,60,89,74,44,78,45,53,41,54,52},
{57,51,73,76,63,32,47,63,46,39,24,46,52,31,48,39,14,69,55,51,60,58,56,42,30},
{67,30,75,62,27,43,50,51,36,49,53,47,62,31,64,36,56,88,51,46,39,69,52,58,76},
{76,53,47,85,43,50,43,20,57,16,26,47,67,50,57,33,50,40,49,60,37,84,75,32,24},
{83,64,87,57,47,85,17,45,34,43,44,41,28,59,60,81,17,64,58,66,66,20,50,29,21},
{41,56,22,46,62,44,27,60,46,26,82,34,50,40,43,36,62,65,39,59,73,77,74,62,52},
{76,68,36,60,57,32,26,64,54,57,71,73,43,26,84,45,27,46,38,61,27,55,76,55,31},
{34,69,47,29,41,73,34,77,21,44,40,55,69,30,59,66, 6,53,68,27,50,65,53,42,57},
{79,34,47,44,48,41,26,38,59,52,59,40,45,68,65,49,59,69,48,63,22,44,54,54,64},
{30,50,26,45,34,54,50,57,42,79,38,76,53,42,68,37,24,74,63,60,49,80,28,66,40},
{50,36,43,59,56,50,71,51,70,73,61,56,58,27,54,37,50,35,64,46,66,77,25,65,30},
{46,64,67,66,78,63,53,20,24,44,71,55,37,71,62,81,42,70,73,80,64,43,39,52,33},
{45,22,58,47,57,67,60,33,56,30,33,63,42,58,52,52,48,61,48,47,71,68,66,52,67},
{43,43,31,44,36,44,29,47,76,45,31,68,70,50,23,63,44,45,25,46,77,71,44,43,65},
{28,36,42,31,21,81,55,54,27,35,48,62,42,34,35,57,48,64,39,76,16, 7,43,71,35},
{48,53,58,57,61,38,51,53,55,55,44,52,37,70,47,36,36,80,74,22,43,80,29, 9,56},
{49,56,33,76,40,44,73,30,24,30,61,57,36,53,48,58,47,52,42,25,63,29,42,50,64},
{54,33,33,66,58,66,56,37,45,21,74,34,23,42,64,38,77,38,77,46,63,36,80,67,55},
{37,62,62,26,41,38,23,65,49,71,81,55,71,50,23,61,73,61,48,62,66,32,57,77,39},
{54,54,62,57,58,39,69,31,55,33,41,52,25,76,54,14,57,53,41, 9,77,42,32,37,28},
{65,83,66,19,41,52,59,49,55,49,59,73,44,39,31,37,49,39,49,40,17,46,65,66,55},
{45,61,32,41,77,20,67,39,35,58,33,49,32,67,41,41,27,54,53,63,65,50,65,35,45},
{50,38,37,48,74,20,33,59,61,34,56,47,46,73,49,33,59,60,70,39,78,12,53,21,55},
{34,76,63,64,65,62,39,52,56,34,59,56,24,74,31,50,37,72,38,55,62,40,69,42,30}
};
#define x_array_max ((18)-1)
#define y_array_max ((18)-1)
#define xy_route (x_array_max y_array_max 1)
void LOOP(int x, int y, int z, int total);
int MAX=0;
int change_line;
int route[2][x_array_max y_array_max 1][2];

void main()
{
int l;
MAX=0;
change_line =1;
LOOP(0,0,0,0);

printf("MAX= m\n",MAX);
printf("route= \n");
for(l=0;l printf("\n");
}
void LOOP(int x, int y, int z, int total){
int lr=0;
if( (x==x_array_max)&& (y==y_array_max) ){
// change_line =1;
// printf("(- -),",x,y);
route[0][z][0]=x;
route[0][z][1]=y;
total =a[x][y];
// printf(" m\n",total);

if(total>MAX){
MAX=total;
for(lr =0; lr route[1][lr][0]=route[0][lr][0];
route[1][lr][1]=route[0][lr][1];
}
printf("MAX= m\n",MAX);
}
}else{
if(y < y_array_max){
// if(change_line){for(lr=0;lr// printf("(- -),",x,y);
route[0][z][0]=x;
route[0][z][1]=y;
LOOP( x , y 1 , z 1 , total a[x][y] );
}

if(x < x_array_max){
// if(change_line){for(lr=0;lr// printf("(- -),",x,y);
route[0][z][0]=x;
route[0][z][1]=y;
LOOP( x 1 , y , z 1 , total a[x][y] );
}
}
}
[/code]

編輯記錄

Eigen非常感謝你^_^：
不好意思，我還要有個需求，就是要列印出走過的路徑要記錄下來，輸出至檔案或是畫面上，可以請你教我怎麼改寫嗎？我明天會測試一下目前的程式，再通知你的，謝謝你唷。

Cindy610

我有Run過了，但是好像結果是出現最大路徑耶！可能是貼到BCB時，有問題還是怎樣？不過我也參考你的寫出一個找出最短路徑的程式了！非常感謝妳唷︿︿以下是我將你的程式碼貼到BCB的內容
PS.因為我都是用Memo1的物件印至畫面上，所以也些你printf的地方，我都換成Memo1->Lines->Add("")了，所以可能我有那裡沒寫對的地方??才會出現結果是找出最大路徑？

[code cpp]
#include
#include
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
const int a[4][4] = {{58, 35, 39, 74},
{45, 55, 46, 27},
{57, 51, 73, 76},
{67, 30, 75, 62}};
#define x_array_max (4)
#define y_array_max (4)
#define xy_route (x_array_max y_array_max 1)
int MAX=0;
int change_line;
//int route[2][x_array_max y_array_max 1][2];
int route[2][x_array_max y_array_max 1][2];

#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
int l;
MAX=0;
change_line =1;
LOOP(0,0,0,0);
Memo1->Lines->Add("MAX=" IntToStr(MAX));
Memo1->Lines->Add("route= ");
for(l=0;l Memo1->Lines->Add(IntToStr(route[1][l][0]) IntToStr(route[1][l][1]));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::LOOP(int x, int y, int z, int total)
{
int lr=0;
if( (x==x_array_max)&& (y==y_array_max) ){
// change_line =1;
// printf("(- -),",x,y);
route[0][z][0]=x;
route[0][z][1]=y;
total =a[x][y];
// printf(" m\n",total);
if(total>MAX){
MAX=total;
for(lr =0; lr route[1][lr][0]=route[0][lr][0];
route[1][lr][1]=route[0][lr][1];
}
Memo1->Lines->Add("MAX= " IntToStr(MAX));
}
}else{
if(y < y_array_max){
// if(change_line){for(lr=0;lr // printf("(- -),",x,y);
route[0][z][0]=x;
route[0][z][1]=y;
LOOP( x , y 1 , z 1 , total a[x][y] );
}
if(x < x_array_max){
// if(change_line){for(lr=0;lr // printf("(- -),",x,y);
route[0][z][0]=x;
route[0][z][1]=y;
LOOP( x 1 , y , z 1 , total a[x][y] );
}
}
}
[/code]

編輯記錄

這就是動態規劃?

------
KUSO 無處不在