基本结构

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法 。

设计步骤

  • 确定状态

解题的前提就是确定题中的状态是什么，一般情况下，动态规划需要开一个数组，数据的每个元素f(i)或者f(i)(j)代表的就是状态。

  • 找到转移公式

f(i)的获值的公式

  • 确定初始条件以及边界条件

他的初始条件，和退出条件

  • 计算结果

    买卖股票的最佳时机

    https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn8fsh/
    1. class Solution {
    2.   public int maxProfit(int[] prices) {
    3.       int len=prices.length;
    4.       //状态 
    5.       int[] clean=new int[len];//没有股票的时候的利润
    6.       int[] input=new int[len];//假设买入了股票
    7.       if(prices.length<=1)
    8.           return 0;
    9.       clean[0]=0;
    10.       input[0]=-prices[0];
    11.       for(int i=1;i<len;i++)
    12.       {
    13.           clean[i]=Math.max(clean[i-1],input[i-1]+prices[i]);//计算如果清空了我们可以获得的利润
    14.           input[i]=Math.max(input[i-1],-prices[i]);//最便宜的买入
    15.       }
    16.       return clean[len-1];
    17.   }
    18. }

    最大子序和

    https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn3cg3/
    class Solution {
  public int maxSubArray(int[] nums) {
      int[] maxlen=new int[nums.length];
      int maxvalue=nums[0];
      maxlen[0]=Math.max(nums[0],0);//状态
      for(int i=1;i<nums.length;i++)
      {
          int temp_value=maxlen[i-1]+nums[i];
          maxlen[i]=Math.max(temp_value,0);//计算是正数的子序列 转移公式
          if(temp_value>maxvalue)
          {
              maxvalue=temp_value;//将最大值返回
          }
      }
      return maxvalue;
  }
}

    打家劫舍

    你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnq4km/

public int rob(int[] nums) {
        //运用动态规划
        //如果偷了该家
        int tou=nums[0];
        int noTou=0;
        for(int i=1;i<nums.length;i++)
        {
            int temp=noTou+nums[i];
            //看上一天偷了和没偷获取最多的money
            noTou=Math.max(noTou,tou);
            tou=temp;
        }
        return Math.max(tou,noTou);
    }