动态规划问题

动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划问题满足三大重要性质

最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

简单dp问题分类

1.简单动态规划算法，即状态方程是用一个维度的变量的描述的，常见的问题如：斐波那契数列，爬台阶问题等

爬台阶问题问题描述： 有一座高度是n级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
状态描述： 我们使用变量n表示台阶的级数，F(n)表示n级台阶一共有多少种走法
状态转移方程与问题分解： 根据每次能跨越的台阶数目：1级台阶或者2级台阶，因为走到N级台阶之前，人一定是处于N-1级台阶或者N-2级台阶。F（n）的走法，一定是n-1级别的台阶的所有的走法和n-2级别台阶的所有走法之和。
F(n） = F(n-1) + F(n-2);

    int climbStairs(int n) {
        vector<int>dp(n+1,0);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp.back();
    }

2.最小路径和问题，常见题型：矩阵最小路径和、三角形最小路径和

leetcode64
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int dp[m][n];
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++)
        {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<n;j++)
        {
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

leetcode120
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）

    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()||triangle[0].empty()) return 0;
        for(int i=1;i<triangle.size();i++)
        {
            for(int j=0;j<triangle[i].size();j++)
            {
                if(j==0)
                    triangle[i][j]+=triangle[i-1][j];
                else if(j==triangle[i].size()-1)
                    triangle[i][j]+=triangle[i-1][j-1];
                else
                    triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1]);
            }
        }
        return *min_element(triangle.back().begin(),triangle.back().end());   
    }

3.背包问题

一个背包有一定的承重cap，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。
给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值。
测试样例：
[1,2,3],[1,2,3],3,6
返回：6

int maxvalue(vector<int> &weight,vector<int> &value,int n,int m)
{
  vector<int> f(weight.size()+1,0);
  for (int i = 1; i <= n; i++) {
       for (int j = m; j >= 1; j--) {
           if (weight[i] <= j) {
               f[j] = f[j] > f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
           }
       }
  }
}

leetcode 322
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1

    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        if(n<=0 || amount<0) return -1;
        vector<int>dp(amount+1,amount+1);
        dp[0]=0;
        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j<coins.size();j++ )
            {
                if(coins[j]<=i)
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
            }
        }
        return (dp[amount]>amount) ?-1:dp[amount];
    }

4.最长上升子序列问题

leetcode 300
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> dp(nums.size(),1);
        int res=0;
        for(int i=0;i<nums.size();++i)
        {
            for(int j=0;j<i;j++)
            {
            if(nums[i]>nums[j])
                dp[i]=max(dp[i],dp[j]+1);
            }
            res=max(res,dp[i]);
        }
        return res;
    }

5.回文子串问题

leetcode5
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

    string longestPalindrome(string s) {
        if(s.empty()) return "";
        const int n=s.size();
        int dp[n][n];
        int left=0,right=0,len=0;;
        for(int i=0;i<s.size();i++)
        {
            dp[i][i]=1;
            for(int j=0;j<i;i++)
            {
                dp[j][i]= (s[i]==s[j]) &&(i-j<2 || dp[j+1][i-1])；
                if(dp[j][i] && len<i-j+1)
                {
                    len=i-j+1;
                    left=j;
                    right=i;  
                }
            }
            return s.substr(left,right-left+1);
        }
    }

6.最长上升子序列问题(LCS)

leetcode1143
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size()+1;
        int n=text2.size()+1;
        int dp[m][n]={};
        for(int i=1;i<m;++i)
        {
            for(int j=1;j<n;++j)
            {
               if(text1[i-1]==text2[j-1])
               {
                   dp[i][j]=dp[i-1][j-1]+1;
               }
               else
                 dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 
            }
        }
        return dp[m-1][n-1];
    }
};