动态规划解题步骤？
 
判断原问题是否可递归求解
分析递归过程中是否存在重复子问题
采用备忘录法记录重复子问题的解（剪枝）
改用自底向上的递推（动态规划）
 
我们以编辑距离为例来分析上面的步骤：
 
 
 
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 
 
你可以对一个单词进行如下三种操作：
 
 
 
插入一个字符
 删除一个字符
 替换一个字符
 
 
示例 1：
 
 
 
输入：word1 = “horse”, word2 = “ros”
 输出：3
 解释：
 horse -> rorse (将 ‘h’ 替换为 ‘r’)
 rorse -> rose (删除 ‘r’)
 rose -> ros (删除 ‘e’)
 
 
分析：
 
 
 
1、当第一个字符串的第一个字符和第二个字符串的第一个字符相同时，对结果没有增益效果。
 2、当第一个字符串的第一个字符和第二字符串的第一个字符不相同时，有三种情况
 
 
a.插入一个字符
 b.删除一个字符
 c.替换一个字符
 
 
递归加备忘录：
 动态规划：
 

 首先要感谢自己幸运地看到了慕课网上，北大老师的程序设计与算法课。讲得真心不错，推荐一看。
 

 
 
 

 
 
 

 说明：该文章所直接使用的动态规划解题步骤来自上述的课程，不再具体讲解，直接使用。看另外，该文章以步骤的第一步为主，重点讲解无后效性，后面三步不再赘述。
 

 
 
 

 1：把原问题化为子问题。首先考虑的是----“求序列前i个元素的最长递增子序列”，
 即可以定义F（i）=x
 ;x是当前状态的值。进一步分析，虽然，状态的值只有一个，但是到达这个状态的途径有很多，进一步想F（i+1），如果这些不同途径中的某个途径（序列）的最后一个元素比ai+1小，那么F(i+1)就会是更长的子序列；反之，如果不比ai+1小，F(i+1)就不一样了。
 这样，F(i+1)的值不仅与当前状态的值（x）有关了，
 也就不满足无后效性。补充：（无后效性定义）当前的若干个状态的值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前采取哪种手段或经过哪条路径演变到当前这若干个状态无关。
 

 
 
 

 所以，子问题这么划分是不适合用动态规划的。我们接下来换个子问题的设法。 “子问题为以元素ai结尾的最长递增子序列”，即F(ai)=x;这样就保证了，在我们求出了所有的解以后，找出最大的那个就可以了。为什么满足了呢？我们这样想，我们最后会求出所有元素的F(ai)，这些值可能相等可能不等，但不管如何，最后我们要把这些值求最大值，根本不用管到达max(F[ai])经过了那些值，所以只与状态的值有关。
 

 
 
 

 2：确定状态 即每个元素的下标k，因为状态只包含一个变量，所以存储状态值的数组是一维的。即maxvalue【n】;
 

 
 
 

 
 
 

 3:确定一些初始状态的值，在这里我们把初始状态都初始化为1，即以自身结尾的最低要求是一个长度。
 

 
 
 

 4：状态转移方程   网上一搜就看到，不再赘述。
 

 
 
 

 
 
 

 
 
 

 
 
 

 
 

一、题目：
 
 
输入：
 
    第一行：硬币面值数组a
 
    第二行：需组成的金额数m
 
输出：
 
    组成金额m所需的最少硬币数
 
例如：
 
输入：
 
[1,2,5]
 
11
 
输出：
 3
 
二、分析：动态规划解题步骤包含四个部分
 
（1）部分一：确定状态
 
 
（1.1）最后一步
 
 
 
（1.2）子问题
 
 
 
（1.3）递归解法
 
 
 
 
（2）部分二：转移方程
 
 
（3）部分三：初始条件和边界情况
 
 
（4）第四部分：计算顺序（先计算每次计算都会用到的部分）
 
 
 
 
 
（5）小结
 
 
三、代码
 
import java.util.Scanner;

public class Main {
	/*  
测试数据

	 * */
	static int[] a = new int[3];//存放硬币面值（假设有三种面值）
	static int[] dp; //dp[i]组成金额i所需的硬币数（如果无法组成金额i，则设置为无穷）
	static int m;//组成的金额
	public static void main(String[] args){
		//1.输入相关数据
		Scanner sc = new Scanner(System.in);
		for(int i=0;i<3;i++) {
			a[i] = sc.nextInt();
		}
		m = sc.nextInt();
		dp = new int[m+1]; //金额0~m
		
		//2.获取dp数组的值
		dp[0]=0;//设置初值
		getDp();
		
		//3.输出组成金额m所需的硬币数
		System.out.println(dp[m]);
	}
	private static void getDp() {
		for(int i=1;i<=m;i++) {//dp[i],组成金额i所需的硬币数
			dp[i] = Integer.MAX_VALUE;//初始化该位置的值
			for(int j=0;j<a.length;j++) {//可选的硬币面值
				if(i>=a[j] && dp[i-a[j]]!=Integer.MAX_VALUE) {//关键！Integer.MAX_VALUE+1会越界，故排除这种情况；当前的金额数i应>=当前的硬币面值
					dp[i] = Math.min(dp[i-a[j]]+1,dp[i]);//最后dp[i]中存放了所需的最少硬币数。dp[i-a[j]]+1：因为用了硬币a[j],所以用的硬币数+1
				}
			}
		}
		
	}
	
}
	

 
 
 
 
 
 
 
 

动态规划解题套路
 


 
文章目录
 
动态规划解题套路
与贪心区别
动规套路
动规debug
 

 
与贪心区别
 
借鉴【代码随想录】大佬的一句话，动态规划就是由前一个状态推导出来的；贪心是局部选取最优，与前一状态无关。
 
动规套路
 
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
 
动规debug
 
建议打印动规的数组，把状态转移在动规数组上的情况模拟一遍
 
参考：
 
 
 
https://mp.weixin.qq.com/s/ocZwfPlCWrJtVGACqFNAag