题解 | #最小三角路径和#

知识点：

动态规划/DFS

分析：

方法1：

DFS（动态规划都可以用递归解决）

首先分析，相邻的位置在这里指的是下一行中下标与上一层奶牛下标相同或者等于上一层奶牛下标+1的两个位置。那么也就是在每一个坐标进行位置选择的时候，只可以选择（i+1,j)（i+1,j+1），所以就有两种走的方式。

那么就有两种可能的走法，选择其中和最小的走法即可。那么就是

1. int p1 = dfs(cows,i+1,j) + cows[i][j];
2. int p2 = dfs(cows,i+1,j+1) + cows[i][j];

在dfs函数中创建一个f数组用来记录计算过的数据，即记忆化搜索。

详细请看代码

方法2：

dp，动态规划

状态表示：

1. f[i][j] 表示走到坐标i，j时最小的路径和
2. 属性： MIN 最小路径和

状态计算：

1. 由于时两种方法，那么如果走左下方 那么就是f[i][j] = f[i-1][j-1]

2. 如果走右下方 那么就是f[i][j] = f[i-1][j]

3.之所以是上面两个等式，是因为，思考状态的时候去掉当前坐标，因为当前坐标是一样的，那么求出来他们的最小值，再加上当前坐标的值即可。

综上 ，f[i][j] = min(f[i-1][j],f[i-1][j-1]) + cows[i][j];

编程语言：

C++

完整代码：

DFS：运行时间：17ms 占用内存：16252KB

dp动态规划：运行时间：3ms 占用内存：504KB

#include <cstring>
class Solution {
public:
    int f[2010][2010];
    int dfs(vector<vector<int> >& cows,int i,int j){
        if(f[i][j] != -1) return f[i][j];
        if(i == cows.size()) return 0;
        int p1 = dfs(cows,i+1,j) + cows[i][j];
        int p2 = dfs(cows,i+1,j+1) + cows[i][j];
        f[i][j] = min(p1,p2);
        return f[i][j];
    }
    int minimumTotal(vector<vector<int> >& cows) {
        memset(f, -1, sizeof f);
        return dfs(cows,0,0);
    }
};

#include <climits>
#include <cstring>
class Solution {
public:
    int f[2010][2010];
    int w[2010][2010];
    int minimumTotal(vector<vector<int> >& cows) {
        int n = cows.size();
        for(int i = 1;i <= n; i++)
            for(int j = 1;j<=i;j++)
                w[i][j] = cows[i-1][j-1];    
        for (int i = 0; i <= n; i ++ )
            for (int j = 0; j <= i + 1; j ++ )
                f[i][j] = 1e9;
        f[1][1] = w[1][1];     
        for(int i = 2;i <= n; i++)
            for(int j = 1;j<=i;j++)
                f[i][j] = min(f[i-1][j],f[i-1][j-1]) + w[i][j];
        int res = 1e9;
        for(int i = 1;i <= n; i++) res = min(res,f[n][i]);
        return res;
    }
};