동적 프로그래밍 참고 사항

목차

动态规划 동적 프로그래밍

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.[1] In the optimization literature this relationship is called the Bellman equation.

동적 프로그래밍 문제를 해결하기 위한 일반적인 프로세스

 #state of original problem
 state_original_problem = 11

 #dp array
 dp = [some big value] * (state_original_problem+1)

 #base state
 dp[0] = dp[1] = 0

 #from bottom to top
 for i in range (2,len(dp)):
   dp[i] = min(dp[i-1]+2,dp[i-2]+1)

 return dp[-1]

   dp_i = 0 #dp[n-2]
   dp_j = 0 #dp[n-1]

   for i in range(2,n+1):
     dp_n =  min(dp_i+1,dp_j+2)
     dp_i = dp_j
     dp_j = dp_n

   return dp_j

예

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

heights[i][j]代表[i，j]的高度
heights[i][j] = matrix[i][j]=='1'? heights[i-1][j] + 1:0

dp[i][j][k] 代表以[i,j]为右下角，高度为k可以组成的最大面积
dp[i][j][k] = matrix[i][j]=='1'? dp[i][j-1][k] + k : 0

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = 0;
        if (n > 0) { m = matrix[0].size(); }
        vector<vector<int>> heights(n + 1,vector<int>(m + 1,0));
        vector<vector<vector<int>>> dp(n + 1,vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (matrix[i-1][j-1] == '0') { continue; }
                heights[i][j] = heights[i-1][j] + 1;
                for (int k = 1; k <= heights[i][j]; k++) {
                    dp[i][j][k] = dp[i][j-1][k] + k;
                    ans = max(ans, dp[i][j][k]);
                }
            }
        }
        return ans;
    }
};