一、简单DP

礼物最大价值（矩阵贪心类题目）剑指 Offer 47

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        for(int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == 0 && j ==0) {
                    continue;
                }
                if (i == 0) {
                    grid[i][j] += grid[i][j - 1];
                }
                else if (j == 0) {
                    grid[i][j] += grid[i - 1][j];
                }
                else {
                    grid[i][j] += max(grid[i][j - 1], grid[i - 1][j]);
                }
            }
        }
        return grid[m - 1][n - 1];
    }
};

时间复杂度 O(MN)：M, N分别为矩阵行高、列宽；动态规划需遍历整个grid矩阵，使用 O(MN)时间。
空间复杂度 O(1)：原地修改使用常数大小的额外空间。

爬楼梯 剑指 Offer 10- II.

class Solution {
public:
    int numWays(int n) {
        if (n == 0 || n == 1) 
        {
            return 1;    
        }
        if (n == 2)
        {
            return 2;
        }
        int a = 1, b = 2;
        int res = 0, MOD = 1000000007;
        for (int i = 3; i <= n; i++)
        {
            res = (a + b) % MOD;
            a = b;
            b = res;
        }
        return res ;
    }
};

时间复杂度O(n)，空间复杂度O(1)

二、字符串+DP

编辑距离 leetcode 72

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        if (m * n == 0) {
            return m + n;
        }
        int dp[m + 1][n + 1];

        for (int i = 0; i <= m; i++)
        {
            dp[i][0] = i;    // 当word2为空时, word1需要删掉i个字符
        }
        for (int j = 0; j <= n; j++)
        {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                int flag = (word1[i - 1] == word2[j - 1] ? 0 : 1);
                dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + flag));
            }
        }
        return dp[m][n];
    }
};

最长公共子序列 leetcode 1143

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        if (m * n == 0) {
           return 0;
        }
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        // vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
        
        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][n];
    }
};

最长回文字串 [leetcode 5]

最长不重复子串 [leetcode 3]

动态规划面试题