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

三角形最小路径和

https://www.nowcoder.com/practice/c9d44b73dc7c4dbfa4272224b1f9b42c

使用动态规划,从最后一个状态进行分解,设 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表。可能会忽视的点就是要根据转移方程确定填充方式,因为动态规划的当前状态之和前状态相关。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
白火同学:只是实习的话,你这份简历应该也差不多了。真要优化的话,因为面实习的话,没有开发经验,面试更重视技术栈水平。 1、重视JavaSE的基础吧,集合、泛型算是比较基础的基础,多线程、反射、JVM内存模型才是基础; 2、技术栈写到具体的点,比如Elasticsearch的使用写到某个点,限制面试官自由发挥,防止问了相关问题最后又答不上,如果真没把握建议不写,降低面试官的心理预期; 3、技术栈不要重复,比如技术栈第二条和第八条可以合并改为“熟悉Redis中间件,包括基本数据结构、缓存策略、持久化机制,了解缓存三剑客及其解决方案,并有相关项目经验。”; 4、项目指标量化,比如“达到xx秒的响应速度”(不过这个就有点偏校招社招的要求了,实习简历不写也无伤大雅)。
点赞 评论 收藏
分享
06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务