알고리즘 프로그래밍 문제 총결산(2) 동적 기획

동적 기획의 일반적인 사고방식은 큰 문제를 작은 문제로 분해하는 것이다. 즉, 한 문제를 한 걸음 한 걸음 해결하는 하위 문제로 고려하는 것이다.https://blog.csdn.net/m0_37789876/article/details/82853572이 블로그는 동적 기획 문제에 대한 해설이 괜찮다.
1. leetcode(53)의 가장 큰 하위 서열과 정수 그룹을 지정한nums에서 가장 큰 것과 가장 큰 연속적인 하위 그룹을 찾으십시오. (하위 그룹은 최소한 하나의 요소를 포함합니다.) 최대 및 최대 하위 그룹을 되돌려줍니다.
예: 입력: [-2,1,-3,4,-1,2,1,-5,4], 출력: 6 해석: 연속 서브 그룹 [4,-1,2,1]의 크기와 최대는 6이다.동적 기획의 사상을 이용하여 문제를nums[i]로 끝날 때 구성할 수 있는 최대 연속 서브 그룹으로 나누고 m[i]로 가정하면 m[i]=max(m[i-1]+nums[i],nums[i])로 나눈다.m[i]를nums[i]로 간주하고 프로그램은 다음과 같이 쓸 수 있습니다.

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:return 0
        
        for i in range(1,len(nums)):
            nums[i] = max(nums[i-1]+nums[i],nums[i])
        return max(nums)

2. leetcode(62)의 다른 경로에서 로봇은 mxn 격자의 왼쪽 상단에 위치하고 (시작점은 아래 그림에서'Start'로 표시됨)로봇은 매번 아래로 또는 오른쪽으로 한 걸음만 이동할 수 있다.로봇이 메쉬의 오른쪽 아래 구석에 도달하려고 한다(아래 그림에서 "Finish"로 표시됨).-- 총 몇 개의 다른 경로가 있나.https://leetcode-cn.com/problems/unique-paths/
이 문제 역시 귀속적인 방법으로 해답을 구할 수 있고 아래의 해답 방법은 중복 계산이 존재하여 최적화할 수 있다.dp[i][j]를 설정하여 i행 j열에 도달하는 가장 많은 경로수를 동태적으로 계획하고 한 걸음 한 걸음 분해하는 사상에 따라 로봇이 오른쪽으로 이동하거나 아래로 이동할 수 있기 때문에 이 점에 도달하는 방법은 (i-1, j)와 (i, j-1) 두 점에서만 가능하다.그래서 dp[i][j]=dp[i-1][j]+dp[i][j-1]가 있다.그리고 모든 경계는 하나의 주법만 있고 첫 번째 줄은 모두 오른쪽으로 가고 첫 번째 열은 모두 아래로 가기 때문에 모두 1로 설정한다.절차는 다음과 같습니다.

class Solution(object):
    def uniquePaths(self,m, n):
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[-1][-1]

3. leetcode(63) 다른 경로 II
로봇은 m x n 메쉬의 왼쪽 상단 모서리에 있습니다(시작점은 다음 그림에서 Start로 표시됨).
로봇은 매번 아래로 또는 오른쪽으로 한 걸음만 이동할 수 있다.로봇이 메쉬의 오른쪽 아래 구석에 도달하려고 한다(아래 그림에서 "Finish"로 표시됨).
지금 격자 안에 장애물이 있다는 것을 고려하다.그러면 왼쪽 상단에서 오른쪽 하단까지 몇 개의 다른 경로가 있습니까?그물 속의 장애물과 빈 위치는 각각 1과 0으로 표시한다.
설명: m와 n의 값은 모두 100을 넘지 않는다.
예1:
입력: [[0,0,0], [0,1,0], [0,0,0] 출력: 2 해석: 3x3 격자 한가운데에 장애물이 있다.왼쪽 상단에서 오른쪽 하단까지 2개의 다른 경로가 있습니다.
4

오른쪽-> 오른쪽-> 아래로-> 아래로

4

아래로-> 아래로-> 오른쪽-> 오른쪽으로

https://leetcode-cn.com/problems/unique-paths-ii사고방식: 이 프로그램에서 matrix[0][1]=1과 matrix[1][0]=1의 의미는 같고 모두 초기에 하나의 기점을 주는 값이다. 그리고 경계의 요소를 고려하여 여기에 행수와 열수를 모두 1로 추가했다.장애물에 부딪히면 장애물이라는 점의 값을 0으로 설정할 수 있다는 뜻으로 이 점에서 출발할 노선이 없다는 뜻이다.

if obstacleGrid[i-1][j-1] != 1：
	matrix[i][j] = matrix[i-1][j] + matrix[i][j - 1]  
else：
	0

절차는 다음과 같습니다.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        matrix = [[0 for _ in range(len(obstacleGrid[0])+1)]
                  for _ in range(len(obstacleGrid)+1)]
        matrix[0][1] = 1
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
           	 	if obstacleGrid[i-1][j-1] != 1：
                	matrix[i][j] = matrix[i-1][j] + matrix[i][j - 1]
                else:
                	0
        return matrix[-1][-1]

미완성