动态规划

 

一些算法举例

动态规划

买卖股票的最佳时机

给定一个数组,它的第i个元素是一支给定股票第i天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意: 你不能再买入股票前卖出股票。

  • 示例
输入:[7,1,5,3,6,4]
输出: 5
解释: 在第2天(股票价格=1)的时候买入,在第5天(=6),最大利润=6-1=5.注意利润不可能是7-1

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下,没有交易完成,所以利润为0.
  • 思路

需要找到最小的谷之后的最大的峰。 我们可以维持两个变量——minprice 和 maxprofit,它们分别对应迄今为止所得到的最小的谷值和最大的利润(卖出价格与最低价格之间的最大差值)。

  • 解法
func maxProfit(_ prices: [Int]) -> Int {
  var minPrice = Int.max
  var maxProfit = 0
  for i in 0..<prices.count {
    if prices[i] < minPrice {
      minPrice = prices[i]
    } else if prices[i] - minPrice > maxProfit {
      maxProfit = prices[i]-minPrice
    }
  }

  return maxProfit
}
  • 结果

print(solution.maxProfit([7,1,5,3,6,4]))

5

买卖股票的最佳时机II

  • 示例
输入:[7,1,5,3,6,4]
输出:7
解释:在第2天(=1)买入,第三天(=5)卖出,利润4,然后在第4天(=3)买入,第5天(=6)卖出,利润3
总利润3+4=7
  • 思路

在斜坡上爬升并持续增加从交易中获得的利润

leetcode_maxprofit

  • 解法
func maxProfitII(_ prices: [Int]) -> Int {
  if prices.count < 2 {
    return 0
  }

  var maxProfit = 0
  for i in 1..<prices.count {
    if prices[i] > prices[i-1] {
      maxProfit += prices[i]-prices[i-1]
    }
  }
  return maxProfit
}
  • 结果

print(solution.maxProfitII([7,1,5,3,6,4]))

7

滑动窗口最大值

给定一个Int窗口,实时的输出窗口最大的元素

  • 示例
输入:k=3,nums=[1,3,-1,-3,5,3,6]
输出:[3,3,5,5,6]
  • 思路

窗口为3个位置,只要有一个最大值进来,比他早的元素永远没有出头之日,所以可以直接忽略掉。

  • 解法
func findMaxInWindow(_ count: Int, _ nums: [Int]) -> [Int] {
  var res = [Int]()

  if nums.count < 0 {
    return []
  }

  var maxNum = Int.min

  if nums.count < count {
    for i in 0..<nums.count {
      if nums[i] > maxNum {
        maxNum = nums[i]
      }
    }

    res.append(maxNum)

    return res
  }

  for i in 0..<count {
    if nums[i] > maxNum {
      maxNum = nums[i]
    }
  }

  res.append(maxNum)

  for j in (nums.count-count-1)..<nums.count {
    if nums[j] > maxNum {
      maxNum = nums[j]
    }

    res.append(maxNum)
  }

  return res
}
  • 结果

let r15 = solution.findMaxInWindow(3, [1,3,-1,-3,5,3,6])

print(r15)

[3, 3, 5, 5, 6]

生成小括号字符串

给定固定长度,比如n,生成所有合法的小括号组成形式

  • 示例
输入: n=3
输出: ["((()))", "(()())", "(())()", "()(())", "()()()"]
  • 思路

采用递归,但是要注意,左右括号肯定都是为n个,并且左括号可以随意加(不超过n),但是右括号必须要在左括号大于右括号的时候才可以输入,然后递归即可

  • 解法
func generateParenthesis(_ count: Int) -> [String] {
  var res: [String] = [String]()
  _gen(0, 0, count, "", &res)
  return res
}

func _gen(_ left: Int, _ right: Int, _ count: Int, _ result: String, _ res: inout [String]) {
  //递归出口
  if left == count && right == count {
    res.append(result)
  }

  if left < count {
    _gen(left+1, right, count, result+"(", &res)
  }

  if left > right && right < count {
    _gen(left, right+1, count, result+")", &res)
  }
}
  • 结果

let r16 = solution.generateParenthesis(3)

print(r16)

[”((()))”, “(()())”, “(())()”, “()(())”, “()()()”]

最小路径问题

一个Int型的二维数组(m*n),>0,每个值表明距离,左上角记为【0,0】,右下角记为【m,n】,每个数字只能向右或者向下进行,求出从【0,0】->【m,n】的最小路径。

  • 示例

输入(Path):

1 1 3
2 3 2
5 1 2
10 1 5

输出:

1-1-3-1-1-5 = 12(最短路径)
  • 思路

采用DP的方式。 状态定义:建立一个同维状态数组DP,相应的位置表示到达此位置的最短路径,如DP[i][j]表示到达Path[i][j]的最短路径; 状态转移方程:DP[0][0]没有选择,肯定就是等于Path[0][0],由于只能向右或者向左行进,所以DP[i][j]只能从Path[i][j-1]或者Path[i-1][j]这两个节点过来的,而当下Path[i][j]的值是固定的。所以DP[i][j]=min{DP[i][j-1], DP[i-1][j]}+Path[i][j]

注:DP[i][j-1]存放的就是到达Path[i][j-1]的最小路径值

第一行和第一列都是比较特殊的存在,只需要累加即能得出路径,如:DP[0][j]=DP[0][j-1]+Path[0][j]

  • 实现
/*
 *一个Int型的二维数组(m*n),>0,每个值表明距离,左上角记为【0,0】,右下角记为【m,n】,每个数字只能向右或者向下进行,求出从【0,0】->【m,n】的最小路径。
 */
func findMinimumPath(inPath path: [[Int]]) -> Int {
    if path.count<=0 {
        return -1
    }
    
    var DP=[[Int]](repeating: [Int](repeating: 0, count: path[0].count), count: path.count)
    
    var rls=DP[0][0];
    
    var row=path[0][0]
    //初始化第一行DP
    for j in 1..<path[0].count {
        DP[0][j]=row+path[0][j]
        row=DP[0][j]
    }
    
    var col=path[0][0]
    //初始化第一列DP
    for i in 1..<path.count {
        DP[i][0]=col+path[i][0]
        col=DP[i][0]
    }
    
    //初始化剩余部分
    for i in 1..<path.count {
        for j in 1..<path[i].count {
            DP[i][j]=min(DP[i-1][j], DP[i][j-1])+path[i][j]
            rls=DP[i][j]
        }
    }
    
    print("findMinimumPath is: \(rls)")
    return rls;
}
  • 结果
let path=[
            [1, 1, 3],
            [2, 3, 2],
            [5, 1, 2],
            [10, 1, 5],
        ]
        
let _=findMinimumPath(inPath: path)

> findMinimumPath is: 12