动态规划理论学习

/**
 * @description: dp课第二节，案例回溯法求解
 * @author: michael ming
 * @date: 2019/7/19 19:55
 * @modified by: 
 */
#include <iostream>
#define N 4//地图大小
#define k (2*N-1)//需要走的步数
using namespace std;
int selectWay[k], shortestWay[k];
void step(int (*map)[N], int s, int &mins, int r, int c, int idx)
{
    selectWay[idx++] = map[r][c];//记录选择的路
    if(r == N-1 && c == N-1)
    {
        if(s < mins)
        {
            mins = s;//更新最小的总路程
            for(int i = 0; i < k; ++i)//把最终的路线记录下来
                shortestWay[i] = selectWay[i];
        }
        return;
    }
    if(r == N || c == N)
        return;//走出地图边界了
    step(map,s+map[r+1][c],mins,r+1,c,idx);//往下走
    step(map,s+map[r][c+1],mins,r,c+1,idx);//往右走
}
int main()
{
    int s = 0, mins = 65535;
    int map[N][N] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3};
    step(map,s+map[0][0],mins,0,0,0);
    cout << "最短路径是：" << mins << endl;
    cout << "走过的点的距离分别是：" << endl;
    for(int i = 0; i < k; ++i)
        cout << shortestWay[i] << " ";
    return 0;
}

/**
 * @description: dp 状态方程 递归
 * @author: michael ming
 * @date: 2019/7/20 9:35
 * @modified by: 
 */
#include <iostream>
#include <stack>
#define N 4//地图大小
using namespace std;
int states [N][N];
void printShortestWay(int (*map)[N])
{
    stack<int> path;
    path.push(map[N-1][N-1]);//终点
    for(int i = N-1,j = N-1; j != 0 && i != 0; )
    {
        if(states[i][j]-map[i][j] == states[i-1][j])
            path.push(map[--i][j]);//从上面过来的
        else
            path.push(map[i][--j]);//从左边过来的
    }
    path.push(map[0][0]);//起点
    cout << "走过的点的距离分别是：" << endl;
    while(!path.empty())//栈逆序弹出路径
    {
        cout << path.top() << " ";
        path.pop();
    }
}
int minDist(int (*map)[N], int i, int j)//从起点到i,j点的最小距离
{
    if(i == 0 && j == 0)//从起点到起点，返回该位置数值
        return map[0][0];
    if(states[i][j] > 0)//遇到算过的，直接返回结果
        return states[i][j];
    int minLeft, minUp;
    minLeft = minUp = 65535;
    if(j-1 >= 0)
        minLeft = minDist(map,i,j-1);//点左边的点的最小距离
    if(i-1 >= 0)
        minUp = minDist(map,i-1,j);//点上面的点的最小距离
    int currMinDist = map[i][j]+min(minLeft,minUp);
    states[i][j] = currMinDist;//备忘录更新
    return currMinDist;
}
int main()
{
    int map[N][N] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3};
    cout << "最短路径是：" << minDist(map,N-1,N-1) << endl;
    printShortestWay(map);
    return 0;
}