【算法日记】从零开始认识动态规划（一）

class Solution {
public:
    int tribonacci(int n) {
        if(n < 3)
        {
            if(n == 0) return 0;
            else if(n == 1) return 1;
            else if(n == 2) return 1;
            else return 0;
        }
        vector<int> cnt(n + 1);
        cnt[0] = 0;
        cnt[1] = 1;
        cnt[2] = 1;
        for(int i = 3 ; i <= n ; i++)
            cnt[i] = cnt[i - 3] + cnt[i - 2] + cnt[i - 1];
        return cnt.back();
    }
};

class Solution {
public:
    int numDecodings(string s) {
        //动态规划
        //进行初始化
        vector<int> dp(s.size() , 0);
        dp[0] = s[0] != '0';
        if(s.size() == 1) return dp[0];

        if(s[0] != '0' && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0')*10 + s[1] - '0';
        if( 10 <= t && t <= 26) dp[1] += 1;

        //进行处理
        for(int i = 2 ; i < s.size() ; i++)
        {
            //解析一个数字
            if(s[i] != '0') dp[i] += dp[i - 1];
            //解析两个数字
            int t = (s[i-1] - '0') * 10 + s[i] - '0';
            if( 10 <= t && t <= 26) dp[i] += dp[i-2];
        }

        return dp[s.size() - 1];
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        //动态规划解决
        //首先总结状态转换方程
        //走到第（i,j）位置有两种方法从 (i-1 , j) (i , j-1)走过来
        //T(i , j) = T(i-1 , j) + T(i , j-1)
        //进行初始化 --- 只需要初始化(0 , 1)位置即可
        // 0 1 0 0 0
        // 0 
        vector<vector<int>> dp(m+1 , vector<int>(n+1 , 0));
        dp[0][1] = 1;
        for(int i = 1 ; i < m+1 ; i++)
        {
            for(int j = 1 ; j < n+1 ; j++)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        //动态规划解决
        //T(i,j) = max(T(i-1,j) , T(i,j-1)) + f(i , j)
        //首先建表解决初始化问题
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>> dp(m+1 , vector<int>(n+1 , 0));
        //进行处理
        for(int i = 1 ; i < m+1 ; i++)
        {
            for(int j = 1 ; j < n+1 ; j++)
            {
                dp[i][j] = max(dp[i-1][j] ,  dp[i][j-1]) + frame[i-1][j-1];
            }
        }

        return dp[m][n];
    }
};

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& d) {
        //动态规划解决问题
        //建表进行初始化
        int m = d.size();
        int n = d[0].size();
        //dp表 --- 表示从这里走到终点至少需要多少血量
        vector<vector<int>> dp(m+1 , vector<int>(n+1, INT_MAX));
        dp[m][n-1] = 1;
        dp[m-1][n] = 1;
        //进行处理
        //0 -3 1
        //0  1 0
        for(int i = m - 1 ; i >= 0 ; i--)
        {
            for(int j = n - 1 ; j >= 0 ;j--)
            {
                dp[i][j] = min(dp[i+1][j] , dp[i][j+1]) - d[i][j];
                dp[i][j] = max(1 , dp[i][j]);//至少需要1滴血量
            }
        }
       
        return dp[0][0];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //对于每一天来说有三种状态
        //买入 可交易 冷冻
        //0    1   2
        int n = prices.size();
        //建立dp表
        vector<vector<int>> dp(n ,  vector<int>(3));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        //进行处理
        for(int i = 1 ; i < n ; i++)
        {
            //该天之后是买入状态 
            dp[i][0] = max(dp[i-1][0] , dp[i-1][1] - prices[i]);
            //该天之后是“可交易”状态 
            dp[i][1] = max(dp[i-1][2] , dp[i-1][1]);
            //该天之后是“冷冻”状态
            dp[i][2] = dp[i-1][0] + prices[i];
        }
        return max(dp[n-1][1] , dp[n-1][2]);
    }
};

class Solution {
public:
    int maxProfit(int k, vector<int>& p) {
        //动态规划
        //首先分析状态情况
        //建表
        int n = p.size();
        vector<vector<int>> f(n , vector<int>(k+1 , 0));
        vector<vector<int>> g(n , vector<int>(k+1 , 0));
        //进行初始化
        f[0][0] = -p[0];
        //每个位置赋予一个极小值
        for(int i = 1 ; i < k+1 ; i++)
            f[0][i] =  -0x3f3f3f;
        g[0][0] = 0;
        for(int i = 1 ; i < k+1 ; i++)
            g[0][i] =  -0x3f3f3f;
        //进行处理
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j <= k ; j++)
            {
                f[i][j] = max(f[i-1][j] , g[i-1][j]-p[i]);
                g[i][j] = g[i-1][j];
                //只有 大于0次的交易次数才能进行该步操作 边界条件限制
                if(j-1 >=0) g[i][j] = max(g[i][j], f[i-1][j-1] + p[i]);
            }
        }

        //返回g的最后一列
        int ret = 0;
        for(int j = 0 ; j <= k ; j++)
        {
            ret = max(g[n-1][j] , ret);
        }
        return ret;
    
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() <= 0) return 0;
        //动态规划解决问题
        //对于一个位置有两种选择 偷or不偷
        int n = nums.size();
        //         选择偷第一家                            不偷第一家
        return max(nums[0] + robhelper(nums , 2 , n-2) , robhelper(nums , 1 , n - 1));
    }
    //子问题解决
    int robhelper(vector<int>& nums , int left , int right)
    {
        if(left > right) return 0;
        int n = right - left + 1;
        vector<int> f(n , 0);//偷该家的最大金额
        vector<int> g(n , 0);//不偷该家的最大金额
        // 2 3
        // 0 2
        f[0] = nums[left];
        g[0] = 0;
        //对于第一个位置偷还是不偷有两种可能
        //偷第一个位置
        for(int i = 1 ; i < n ; i++)
        {
            //对于不偷此位置的情况：
            //[i-1]可以是偷或者不偷
            g[i] = max(f[i-1] , g[i-1]);
            //偷此位置那么前一个位置就不能选择
            f[i] = g[i-1] + nums[left + i];
        }

        return max(g[n-1] , f[n-1]);
    }
};