动态规划(4)

阅读量：

文章结构概览

- 42. 接雨水
  - - 解题思路
    - c++ 实现
  - 64. 最小路径和
  - - 解题思路
    - c++ 实现
  - 62 不同路径
  - - 解题思路
    - c++ 实现
  - 5 最长回文子串
  - - 解题思路
    - c++ 实现
  - 221 最大正方形
  - - 解题思路
    - c++ 实现

42. 接雨水

题目：假设有 n 个非负整数，分别表示宽度为 1 的柱子的高度，要求根据这些柱子的排列方式，计算在下雨后能够收集到的雨水总量。

示例:

在这里插入图片描述

解题思路分析

采用动态规划(DP)途径进行求解
- 当前位置所承接的水量计算方式为： $min(Left_{max},Right_{max})-CurrHeight$
- 首先对数组进行从左至右的扫描，以确定每个位置左侧所有柱子高度中的最大值 $Left_{max}$ ；

全部评论 (0)

还没有任何评论哟~