算法解题思路-动态规划-一一网

这是我参与新手入门的第1篇文章

前言

空间里有位客户，天天为女儿朗读小故事打卡。从刚开始的七八天、到几十天，再到如今的102天。深有感触，感叹时光飞逝，感慨客户以及他女儿的自律、坚持。受其感染，于是我便定下一个小目标——每天至少写一题算法！！！

就近期做算法题遇到的常见的解题思路：

1.各种排序算法

2.指针、位处理

3.动态规划

今天就动态规划做个总结。

概念

某活动的过程分成若干个互相联系的阶段，每个阶段都做出决策使整个过程达到最好的活动效果。称这种解决多阶段决策最优化的过程为动态规划方法。

动态规划的基本思路：将问题分解成若干个相互联系的子问题，用一个表来记录已经解决的子问题的答案，然后从子问题的答案中得到原问题的答案。

直接结合题目分析：

题目

三角形最小路径和

给定一个三角形triangle，找到自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上层结点下标相同或等于上一层结点下标+1的两个结点。也就是说，如果正位于当前行的下标i,那么下一步可以移动到下一行的下标i或i+1。

示例：

输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为11(即,2 + 3 + 5 + 1 = 11)
复制代码

分析

求最小路径和分解成小问题：从triangle顶部到底部所有位置的任意方式的和。
从小问题取出最小值则为最小路径和。

思路：

用f[i][j]表示从triangle顶部走到(i,j)的路径和。(i,j)表示从0开始编号的第i行第j列的位置。则用函数表示：

f[i][j] = Math.min(f[i-1][j-1],f[i-1][j]) + triangle[i][j]

两种特殊情况:

当到第i行最左侧时，只能从i-1行的最左侧走来，即

f[i][0]=f[i-1][0]+triangle[i][0]
当到第i行最右侧时，只能从i-1行的最右侧走来，即

f[i][i]=f[i-1][i-1]+triangle[i][i]

f[n-1][0]–f[n-1][n-1]的最小值即为最小路径和，n是triangle的行数。

代码

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let n = triangle.length;
    //生成类似triangle,初始值为0的二维数组
    let f = Array.apply(null, Array(n)).map((t, i) => Array(i + 1).fill(0));
    f[0][0] = triangle[0][0];
    //求每个顶部到底部的和(子问题)
    for (let i = 1; i < n; ++i) {
        f[i][0] = f[i - 1][0] + triangle[i][0];
        for (let j = 1; j < i; ++j) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i];
    }
    let minTotal = f[n - 1][0];
    //子问题中最优解
    for (let i = 1; i < n; ++i) {
        minTotal = Math.min(minTotal, f[n - 1][i]);
    }
    return minTotal;
};
复制代码