动态规划

青旅半醒 2022-07-12 05:01 333阅读 0赞

首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解由上一个问题推出，受到前面状态的影响）

动态规划解决的步骤:

1.描述最优解的特征

2.递归的定义一个最优解的值

3.自底向上计算最优解的值

4.从已知的信息中构造一个最优解

动态规划求解的一般思路：

判断问题的子结构（也可看作状态），当具有最优子结构时，动态规划可能适用。

求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。分治法则不同，每次递归都产生新的问题。

重新构造一个最优解。

动态规划有一种能够变形-备忘录，它具有通常的动态规划方法的效率，又采用了一种自顶向下的策略。

下面通过一个实际的例子来对动态规划思想进行介绍

有1、3、 5面值的硬币若干，如何用最少的硬币凑够11元？首先将这个问题一般化，如何用最少的硬币凑够 i元??并设d(j)=i,这里的d(j)是一个函数，表示最少需要i个硬币就可凑够j元。

当i=0时，j=0;也即d(0)=0;当i=1,j=1,此时d(1)=d(1-1)+1=1,当i=2,j=2,d(2)=d(2-1)+1=2;当i=3,j=1,此时有两种情况:d(3)=d(3-1)+1=3或者d(3)=d(3-3)+1=1,我们选择最优的那一个，故d(3)=min\{d(3-1)+1, d(3-3)+1\}。到这边一个最优解的特征就被描述出来了。下面我们通过程序来实现这个算法。

package cc;
    
    public class Main {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		int[] a={1,3,5};
    		int total=11;
    		System.out.println(getamount(a,total));
    
    	}
    
    	private static int getamount(int[] a, int total) {
    		// TODO Auto-generated method stub
    		int min[]=new int[total+1];
    		min[0]=0;
    		int minCoin=0;
    		for(int i=1;i<min.length;i++){
    			minCoin=i;
    			for(int j=0;j<a.length;j++){
    				if(a[j]<=i&&min[i-a[j]]+1<minCoin)//(i-a[j])必定>0
    				{
    					minCoin=min[i-a[j]]+1;
    					
    				}
    			}
    			min[i]=minCoin;
    		}
    		return min[11];
    	}
    
    }