java暴力遞歸回溯算法

今天這個問題是我之前一直想解決的，還記得以前第一次上藍橋杯的課的時候，也就是大一高數期中模拟考試那天，下午去上藍橋杯課，遇到這道題，當時寫了寫，根本沒有思路，然後就給大一的模拟考試去了。印象深刻啊，一直沒寫出來。先來說一下題目吧。

問題描述:

如下圖所示的數字三角形，編寫一個程式計算從頂部到底部某一處的一條路徑，使得該路徑數字和最大，輸出路徑和最大值。

3 8

8 1 0

2 7 4 4

4 5 2 6 5

當然什麼是路徑，路徑就是能連着，但是不能跳過，比如7-3-8-7-2就是一條路徑。

輸入:

5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

輸出:

路徑:7-3-8-7-5，最大值:30

算法思想:

這道題啊，其實和馬走日思想很像，首先從0,0這個位置出發，一直走遍整個棋盤(把整體看做一個棋盤)

3 8

8 1 0

2 7 4 4

4 5 2 6 5

棋盤挪過來成這樣的形狀。我輸入放在qipan[][]數組中，然後用一個臨時數組temp[][]和棋盤大小一樣，把這個臨時數組全部初始化為0，走一步把這個數組更新為1(想象成馬走日) 全部走到底，則周遊temp[][]數組，如果temp[][]不為0，即有走的，那麼就輸出棋盤上面對應的棋盤數字。分别用變量sum，和maxv來記錄最大值，當為最大值時要儲存走的狀态，即輸出走的最大值是哪步。最後我是用一個HashMap來儲存所有的取值情況，在主函數中，如果hashmap的值 = maxv，則輸出，最後得到結果。這種暴力解決方法是在資料量不多的情況下好解決，可是資料量多，就用動态規劃來解決。

代碼示例:

package com.zzl.zt;

/*
 * 7
 * 3 8
 * 8 1 0
 * 2 7 4 4
 * 4 5 2 6 5
 */
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
 
public class RouteTest {
    static int qipan[][] = new int[20][20];
    static int temp[][] = new int[20][20];
    static int weizhi[][] = {{1,0},{1,1}}; // 隻能向下走，或者向右下走
    static int step = 1;
    static int sum = 0;
    static int maxv = 0;
    static Map<StringBuffer, Integer> map = new HashMap<StringBuffer, Integer>();
     
 
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        System.out.println("請輸入共有多少行并輸入資料:");
        int n = scn.nextInt(); //總共的行數
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                qipan[i][j] = scn.nextInt();
                temp[i][j] = 0;
            }
        }
        temp[0][0] = step;
        step++;
        move(0,0,n); //把n行數傳進去，要不然不知道行數
         
        //周遊Map集合，一次輸出，作為一個樣本即可
        Iterator it = map.entrySet().iterator(); 
        while (it.hasNext()) { 
            Entry entry = (Entry) it.next(); 
            if(entry.getValue() == Integer.valueOf(maxv)){
                System.out.println(entry.getKey() + "最大值:" + entry.getValue()); 
            }
        } 
    }
    public static void move(int x, int y, int n) {
        int next_x = 0;
        int next_y = 0;
        if(step>n){  //遞歸到了底部
            sum = 0;
            StringBuffer sb = new StringBuffer();
            sb.append("路徑:");
            for(int i=0;i<n;i++){
                for(int j=0;j<=i;j++){
                    if(temp[i][j] !=0){  //也就是說有走過了
                        //這就是一個輸出表示形式
                        if(i==n-1){
                            sb.append(qipan[i][j] + ",");
                        }else{
                            sb.append(qipan[i][j] + "-");
                        }
                        //計算這一趟sum的總值
                        sum = sum+qipan[i][j];
                    }
                }
            }
            //判斷sum是否更大，更大則更新資料
            if(sum>maxv){
                maxv = sum;
            }
            map.put(sb, sum);
        }else{
            for(int i=0;i<2;i++){ //隻有兩個位置可以走，并且這兩個位置都能走，沒有限制條件
                next_x = x+weizhi[i][0];
                next_y = y+weizhi[i][1];
                temp[next_x][next_y] = step;
                step++;
                move(next_x, next_y, n);
                temp[next_x][next_y] = 0;
                step--;
            }
        }
    }
}

資料包

java面試你不知道的事java暴力遞歸回溯算法