Re: [問題] 可停留的路線安排程式
不知道有沒有漏看一些訊息，用程式碼表示我粗淺的想法。
int map[M][M]={0}; //盤面
int table[N+1][M][M]={0}; //DP表格
//設定初始盤面
map[0][0]=40;
map[0][1]=30;
/*
.
.
.
*/
//設定第一天的各種可能情況
for(int i=-1;i<=1;++i)
{
for(int j=-1;j<=1;++j)
{
table[1][M/2+i][M/2+j]=map[M/2+i][M/2+j];
}
}
//開始填表
for(int i=2;i<=N;++i)
{
for(int j=0;j<M;++j)
{
for(int k=0;k<M;++k)
{
table[i][j][k]=findMax(map,table,i,j,k);
}
}
}
int findMax(int map[M][],int table[N+1][M][],int i,int j,int k)
{
//填空
//需處理邊界問題
//需處理當天不能走到的點，在此範例假設table值為0代表無法走到，當天不能走到的
點為table值前一天相鄰點皆為0的點。
return max;
}
※ 引述《DJWS (...)》之銘言：
: ※ 引述《jakeasa123 (啊斑斑)》之銘言：
: : 先前在Python板發了篇文，也獲得了一些提示，但看了好幾天也試做了幾個版本，還是沒能達到目標，於是來此詢問。
: : Python板原文：https://www.ptt.cc/bbs/Python/M.1480482142.A.713.html
: 1. 養不教，父之過。教不嚴，師之惰。
: 不必同情老師和同學。他們都有問題。
: 2. 原文的推文都在狀況外。
: 3. 你的問題可以粗略分成程式問題、算法問題。
: 4. 程式問題就是語文問題，另含一點點數學問題。
: 程式語言變化少，只有for if array recursion，通常都有前例可循，其實不難。
: 由於你沒有提供程式碼，這裡假設你沒有程式方面的問題。
: 5. 算法問題就是數學問題。
: 數學問題最困難的地方，就是變化太多、往往沒有前例可循。
: 比方說，在幾何圖形上畫一條補助線，問題豁然開朗，根本莫名其妙。
: 即便背熟算法課本，遇到新的算法問題，通常還是解不開，不必自責。
:
: 6. 這一題的特色是：
: (1) 分階段：分成一天一天，每天做一件事。
: (2) 有因果：今天的位置，決定了明天的位置（在九宮格內）。
: (3) 可累積：今天的收益，以後列入總收益。
: 通常這種題型，可以用dynamic programming解決。
: 盤面拷貝數份，疊起來，變成三維。
: 一天換一個盤面，往上方走去。
: 程式碼有：一個二維陣列（盤面），兩個二維陣列（dp表格），四層迴圈（填表格）
: 7. 為什麼我會知道那些特色呢？
: 書讀多了、問題看多了，依照經驗歸納出來的。
: 這些特色在不同地方有不同稱呼：
: 例如算法課本裡面的詞彙是「optimal substructure」
: 例如競賽選手所用的詞彙是「無後效性」「狀態轉移」
: 那些特色已經形成了SOP了嗎？
: 就我所知沒有。只能自己看著辦。
: . 為什麼我能聯想到dp呢？
: 因為我曾經遇過類似題目，運氣好。
: 8. 數學問題不只一種解法，這個問題也不只一種解法。
: 如果你想掌握各種解法：
: (1) 靠別人：找一個懂的人，跟他交朋友。往後若有需要，靠交情、花錢請他幫忙。
: (2) 靠自己：讀懂各類算法課程、書籍、論文，情況許可就再念個phd。
: 9. 獲得了「掌握各種解法」的實力之後，有什麼用呢？
: 我看過的有：為興趣、為面試、為逞英雄、為練腦力、為消遣。
: 每個人狀況不一樣，我沒有辦法評論。
: 10. 你們老師同學，也許都想到了這個份上。
: 可能他們已經獲得了「掌握各種解法」的實力。
: 可能他們不想獲得這種實力，因為沒用處、因為關注其他實力、因為太弱、...。
: 因此他們各方評估後，決定簡單教、隨便學就好。
: 與其說他們都有問題，不如說他們都有心思。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.62.74.75
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1481770791.A.71B.html
→
12/15 11:28, , 1F
12/15 11:28, 1F
→
12/15 11:36, , 2F
12/15 11:36, 2F
→
12/15 11:37, , 3F
12/15 11:37, 3F
討論串 (同標題文章)