(1)状态表示:
dp[i][j] :表示第i堆石子到第j堆的最小代价
sum[i][j]:表示第i堆石子到第j堆的质量之和
(2)状态方程:
dp[i][j]=min{ dp[i][k] + dp[k+1][j]+sum[i][j]} for(int k=i; k<j; k++)
(3)边界条件:
当 i = j时, dp[i][j] = 0 // 只有一堆石子,则无需合并
(4)时间复杂度 : O(n*3) //类似于矩阵连乘问题
空间复杂度 : O(n*2)
学习体会:
学习动态规划的很多过程都是在找寻一个问题的最优子结构,一个问题的最优解包含了其子问题的最优解,这启发了我,以后的学习与生活会面临很多选择,我一样需要找到每个人生“子问题”的最优解,动态规划在我看来即是把问题分成很多步,每一步都走到“最优”,最后就能得到整个问题的最优解
同样,重叠子问题也是动态规划的一个要点,在这里我学习到使用备忘录算法,避免每个问题的重复求解,学习与生活中也是一样,不要过多的进行无意义重复,有规划有记录的学习才能高效