还有知乎上的

搞清楚什么是动态规划，和什么时候用动态规划。

p.s.百度百科和算法数上那一大堆看完也没什么意思，不如从实例入手。掌握分析递推关系才是王道。

 集合存储状态+状态转移方程

超级楼梯

共两种爬楼方式——一次上一个台阶&一次上两个台阶，问上到第n阶台阶的方法共多少种。

设状态dp[i]为上i阶台阶的方法种数，dp[1]=1;dp[2]=1;状态转移方程 dp[i]=dp[i-1]+dp[i-2];//上一阶和两阶

有了该递推式，我们就不用递归暴力解决了。（递归开销是真的大

dp[i][j]为到单元格(i,j)的方法数，dp[0][]=1;dp[][0]=1;dp[i][j]=dp[i-1][j]+dp[i][j-1];//向下走和向右走

　　

public int uniquePaths(int m, int n) {        int[][] dp = new int[m][n];                for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (i == 0 || j == 0)                    dp[i][j] = 1;                else {                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];                }            }        }        return dp[m - 1][n - 1];            }

 进阶：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {        int row=obstacleGrid.length;        int col=obstacleGrid[0].length;        int[][] dp=new int[row][col];        if(obstacleGrid[0][0]==1){             return 0;        }        for(int i=0;i

上面几个都是连续型问题，楼梯台阶连续，走的格子连续。

0-1背包问题 

背包的容量j因放入物品的重量w不同，变化非连续，但一般都有额外的空间(表)来存储状态信息。

递归遍历解法：

int []w={15,17,20,12,9,14};    int []p={32,37,46,26,21,30};        public int solve(int i,int n,int j,int max){        if(i
      
       =w[i]){                return Math.max(solve(i+1,n,j-w[i],max+p[i]),solve    (i+1,n,j,max));            }else{                return solve(i+1,n,j,max);            }            }else            return max;    }
      

 

dp[i][j]表示前i件物品恰放入一个容量为j的背包可获得的最大价值dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+p[i]};

public int Packet(int c){        int []w={15,17,20,12,9,14};    　　 int []p={32,37,46,26,21,30};        int packets=w.length;        int [][]dp=new int[packets+1][c+1];        for(int i=0;i<=packets;i++)            for(int j=0;j<=c;j++){                if(i==0||j==0)                    dp[i][j]=0;                else if(j>=w[i-1]){                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i-1]]+p[i-1]);                }else                    dp[i][j]=dp[i-1][j];            }        return dp[packets][c];    }

与贪心算法的每步取”最优“不同，动态规划存储状态信息，并有针对于状态变量的状态转移策略。

 

dp[i]表示截止到i的最大连续字串和，dp[0]=nums[0];dp[i]=max{dp[i-1]+nums[i],nums[i]}

　　

class Solution {    public int maxSubArray(int[] nums){        int len=nums.length;        int[] dp=new int[len];        for(int i=0;i

大佬写的经空间优化后的代码：

public int maxSubArray(int[] nums) {        int res = nums[0];        int sum = 0;        for (int num : nums) {            if (sum > 0)                sum += num;            else                sum = num;            res = Math.max(res, sum);        }        return res;    }