Java教程

动态规划算法

本文主要是介绍动态规划算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

要点

  • 简化问题
  • 减少计算量

套路

  • 定义状态
  • 定义动作
  • 定义边界
  • 缓存已知

硬币找零问题

问题:有三种面值硬币1,3,5,且无限量,请问共需要找零n元,最少需要几枚硬币?
定义状态:minCoinNum(n), 即n元需要的最小硬币数目。
定义动作(分而治之):假如我知道了minCoinNum(n-1)、minCoinNum(n-3)、minCoinNum(n-5)的最少硬币数目,则为n元时,最少硬币数目为:min(minCoinNum(n-1)+1, minCoinNum(n-3)+1, minCoin(n-5)+1)。将n元分为n-1元、n-3元、n-5元,然后选择一个最小的方案。
定义边界:当n<1时,没有余额 ,需要0个硬币,当n等于1、3、5时,需要1个硬币。
缓存已知:minCoinNum(n)作为可能多次计算的数值,由于每次计算都一样,可以将结果缓存起来,避免不必要的计算。

简单的递归版本(无缓存已知的计算状态)代码

package main

import "math"

var coins []int64

func init() {
	coins = []int64{5, 3, 1}
}

func coinSum(amount int64) int64 {
	if amount < 1 {
		return 0
	}

	var minNum int64 = math.MaxInt64
	for _, v := range coins {
		if amount < v {
			continue
		}
		if amount == v {
			return 1
		}
		minNum = int64(math.Min(float64(minNum), float64(coinSum(amount-v)+1)))
	}
	return minNum
}

func main() {
	var amount int64 = 7
	println(coinSum(amount))
}

这篇关于动态规划算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!