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

使用动态规划，从最后一个状态进行分解，设 dp[i][j] 表示在坐标（i，j）处能得到的最小总和，因为下一个点只能是当前点下方一个点，或者右下方一个点，那么 dp[i][j] 的表达式就是   dp[i][j] = min（ dp[i-1][j],dp[i-1][j-1] ） +  c[i][j], c[i][j]表示当前点的数值。
需要注意两个特殊情况，就是当 j = 0 时，dp[i][j] 只能是当前点的数值加上 dp[i-1][j]，因为没有其他位置可以走到这里。还有就是 i = j 的时候，dp[i][j] 只能是当前点数值加上 dp[i-1][j-1]。需要在循环填充dp表的时候设置判断条件。
根据状态转移方程可以看出 dp[i][j] 的状态之和 dp[i-1][j] 和 dp[i-1][j-1] 相关而且只在 i >= j时候有意义，所以在填充dp表的时必须是每一列依次往下填充。


int min(const int a,const int b)
{
    return a<b?a:b;
}


int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) 
{
    // write code here
    int dp[triangleRowLen][triangleRowLen];
    memset(dp, 0, sizeof(dp));
    
    for( int j = 0; j < triangleRowLen; ++j )
    {
        for( int i = j; i < triangleRowLen; ++i )
        {
            if( !j )                                           //j = 0 的情况
            {
                if( !i ) dp[i][j] = triangle[0][0];            //其实dp[0][0]是dp表的初始状态，但是写程序的时候发现在一开始设置好初始状态，for循环不好写，所以直接写进来                            
                else
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
            }
            else if( j != 0 && i == j ) dp[i][j] = dp[i-1][j-1] + triangle[i][j];  //对角线的情况
            else dp[i][j] = min( dp[i-1][j-1],dp[i-1][j] ) + triangle[i][j];       //其余情况
        }
    }
    int res = dp[triangleRowLen-1][0];
    for( int i = 0; i < triangleRowLen; ++i )                                      //比较最后一行的所有数据，选出最小的就是答案
    {
        if( dp[triangleRowLen-1][i] < res ) res = dp[triangleRowLen-1][i];
    }
    
    return res;
}


最近一直在刷动态规划的题目，从刚开始的猪脑过载到自己能写出来，把结题思路记录下来，方便以后回看。之后会把之前刷过的题再整理一遍记录下来，希望秋招的时候考到的全是刷过的。
刷了这么多天的题，对于动态规划的解题思路主要是 从最后一个状态开始分解问题，写出转移方程，根据建立的dp表（一维，二维。。。）所代表的含义确定起始状态。再填充dp表。可能会忽视的点就是要根据转移方程确定填充方式，因为动态规划的当前状态之和前状态相关。