动态规划

原创
03/08 23:23
阅读数 114

动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

题目特点:

计数

- 有多少种方式走到右下角
- 有多少种方法选出k个数使得和是sum

求最大最小值

- 从左上角走到右下角路径的最大数字和
- 最长上升子序列长度

求存在性

- 取石子游戏,先手是否必然取胜
- 能不能选出k个数使得和是sum

栗子一枚(leetcode 322)

2 5 7三种硬币,买一本数尽量少使用硬币个数支付

常规思维:尽量用大的货币,然后处理最后不能整除的数字。

7+7+7 = 21 => 21 + 2 + 2 + 2 =27

6枚硬币。

看似对了,但是其实不是正确答案。

5+5+5+5+7 = 27 ,5枚硬币即可。

状态,在动态规划中的作用属于定海神针

要确定状态应该怎么做?

- 最后一步
- 子问题

最后一步

最后一步就是最优解的最后一个决策

如上题目:

子问题

把问题进行范围缩小

解法1、递归

const INT_MAX = int(^uint(0) >> 1)
func F(x int) int{
	if x=0 {
		return 0
	}
	res = INT_MAX
	if x >=2 {
		res = min(F(x-2)+1, res)
	}
	if x >=5 {
		res = min(F(x-5)+1, res)
	}
	if x >=7 {
		res = min(F(x-7)+1, res)
	}
	return res
}
func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

递归会产生什么问题呢?

运算数目过大时,大量重复计算。效率低下

解法2、动态规划

转移方程:

const INT_MAX = int(^uint(0) >> 1)
func coinChange(coins []int, x int) int{
    if len(coins)==0 || x==0{
        return 0
    }
    dp:=make([]int,x+1) //存储0~x的最优解
	//有f(2),f(4)
    for i:=1;i<=x;i++{
        dp[i]=	INT_MAX
        for c:=range coins{
            if i-coins[c]>=0 && dp[i-coins[c]]!=INT_MAX{
                dp[i]=min(dp[i-coins[c]]+1,dp[i])
            }
        }
    }
    if dp[x]==INT_MAX{
        return -1
    }
    return dp[x]
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

总结

动态规划组成部分

- 确定状态
	最后一步
	转化成子问题
- 转移方程 f(x) = min,max{f(parmas)+-1,...}
- 初始条件和边界情况
	f[0]=0,则不能拼出Y,有f[Y]=无穷
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部