美文网首页动态规划
算法:动态规划(DP)

算法:动态规划(DP)

作者: keloli | 来源:发表于2017-09-02 22:09 被阅读91次

    入门

    在知乎上看到徐凯强 Andy的答案后感觉入门了

    实践

    题目:仅包含0/1的矩阵,求其中最大的全1方阵(不能是矩形)的边长

    题解:matrxi[100][100]表示0/1矩阵,dp[i][j]表示:以matrix[i][j]为右下角,边长最大为min(i,j)的,最大全1方阵的边长
    if(matrix[i][j]==0)
    {
    dp[i][j]=0;
    }
    if(matrix[i][j]==1)
    {
    if(dp[i-1][j]==1&&dp[i][j-1]==1)
    {
    dp[i][j]=dp[i-1][j-1]+1;
    }
    else
    {
    dp[i][j]=1;
    }
    }
    最后dp数组中最大的值即所求的边长

    题目:https://leetcode.com/problems/trapping-rain-water/description/
    Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
    For example,
    Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

    题解:https://leetcode.com/problems/trapping-rain-water/solution/
    核心思想:维护一个区间,当区间缩小时看看是否有一边下降,如果下降则盛雨量增加,否则向内移动短边。

     // https://leetcode.com/problems/trapping-rain-water/solution/
     // Approach #4 Using 2 pointers [Accepted]
     int trap(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
                ++left;
            }
            else {
                height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
                --right;
            }
        }
        return ans;
    }
    

    相关文章

      网友评论

        本文标题:算法:动态规划(DP)

        本文链接:https://www.haomeiwen.com/subject/qfselxtx.html