动态规划解题步骤？

判断原问题是否可递归求解
分析递归过程中是否存在重复子问题
采用备忘录法记录重复子问题的解（剪枝）
改用自底向上的递推（动态规划）

我们以编辑距离为例来分析上面的步骤：

给你两个单词 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.替换一个字符

递归加备忘录：

动态规划：

文章目录
题目特点
四要素
斐波那契数列
暴力法
备忘录优化
DP数组
动态规划详细案例分析
最值类-凑零钱问题(点击查看详细)
计数类-不同路径问题(点击查看详细)
计数类-最长递增子序列(点击查看详细)
存在类-跳跃游戏问题(点击查看详细)
动态规划常见类型

题目特点

计数

有多少种方式走到右下角
有多少种方式选出K个数使得和是Sum


最值

从左上角走到右下角路径的最大值
最长上升子序列的长度


存在性

能不能选出K个数和是Sum
取石子游戏，先手是否必胜



四要素

确定状态。最后一步和子问题
状态转移方程。找出重叠子问题，列出状态转移方程。
初始条件和边界情况
计算顺序

下面将从两个例子来展开介绍，通过斐波那契数列让你明白什么是重叠子问题，通过凑零钱问题分析如何列出状态转移方程。
斐波那契数列
暴力法
public int fib(int N) {

        if (N == 1 || N == 2) {
            return 1;
        }

        return fib(N - 1) + fib(N - 2);

}

以F(10)  为例，发现暴力解法中出现了很多的重复计算，比如F(8)计算了两次。


备忘录优化
耗时主要是重复计算问题，可以通过数组或者哈希表来存储计算结果，充当备忘录。
  //map也可以初始化为一个N+1的数组
   Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    public int fib(int N) {
        if (N<1){
            return 0;
        }
        if (map.get(N) != null) {
            return map.get(N);
        }

        if (N == 1|| N==2) {
            return 1;
        }

        int result = fib(N - 1) + fib(N - 2);

        map.put(N, result);

        return result;

}

DP数组
 public int fib(int n){
        if(n<1){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        int[] dp=new int[n+1];

        dp[1]=dp[2]=1;

        for (int i = 3; i <= n; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
}

状态转移方程，状态是f(n),把f(n)状态转移到f(n-1)和f(n-2)相加。


动态规划详细案例分析
最值类-凑零钱问题(点击查看详细)
计数类-不同路径问题(点击查看详细)
计数类-最长递增子序列(点击查看详细)
存在类-跳跃游戏问题(点击查看详细)
动态规划常见类型

坐标型动态规划
序列性动态规划
划分型动态规划
区间型动态规划
背包型动态规划
最长上升子序列动态规划
博弈型动态规划
综合性动态规划

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




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


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：状态转移方程   网上一搜就看到，不再赘述。

动态规划解题步骤
1.定义子问题：

什么可以算得上有子问题，可以用动态规划解决的问题呢？例如在打家劫舍的算法题中，问题可以被拆分为各个子问题，子问题是打劫前k家能得到的最大金额。假设一共有 n 个房子的话，就一共有 n个子问题。动态规划实际上就是通过求这一堆子问题的解，来求出原问题的解。这要求子问题需要具备两个性质：
（1）原问题要能由子问题表示。例如这道小偷问题中，k=n 时实际上就是原问题。否则，解了半天子问题还是解不出原问题，那子问题岂不是白解了。

（2）一个子问题的解要能通过其他子问题的解求出。例如这道小偷问题中，f(k)可以由 f(k-1)和 f(k-2) 求出。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题，那么这道题实际上没法用动态规划解。

2.写子问题的递推关系：

子问题之间存在一种递推关系。第k个子问题的结果是由第k-1或者k-2个子问题的结果得出的。

3.确定DP数组的计算顺序：

DP 数组也可以叫”子问题数组”，因为 DP 数组中的每一个元素都对应一个子问题。dp[k] 对应子问题 f(k)，即偷前 k 间房子的最大金额。

4.空间优化

案例：（leetcode198）

代码：
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        int[] max = new int[len];
        if(len == 0){
            return 0;
        }
        if(len ==1){
            return nums[0];
        }
        max[0] = nums[0];
        for(int i=1;i<len;i++){
            max[i] = Math.max(max[i-1],(nums[i]+((i-2<0) ? 0:max[i-2]))) ;
        }
        return max[len-1];
    }
}