石子游戏

  1. 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
  3. 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
  5. 亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
  7. 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
  1. class Solution {
  2. public:
  3.     bool stoneGame(vector<int>& piles) {
  4.         const int length = piles.size();
  5.         int result[length][length];
  6.         //只有一个人的时候最多得分
  7.         for(int i = 0; i < length; i++){
  8.             result[i][i] = piles[i];
  9.         }
  10.         //当集合中有两个数的时候，先选的人拿大数
  11.         for(int i = 0; i < length - 1; i++){
  12.             result[i][i + 1] = abs(piles[i] - piles[i + 1]);
  13.         }
  14.         for(int i = length - 3; i >= 0; i--){
  15.             for(int j = i + 2; j < length; j++){
  16.                 result[i][j] = max(piles[i] - result[i + 1][j], piles[j] - result[i][j - 1]);
  17.             }
  18.         }
  19.         return result[0][length - 1] > 0;
  20.     }
  21. };

最大带权路径

  1. 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

我这种写法是把棋盘横过来了

  1. class Solution {
  2. public:
  3.     int maxValue(vector<vector<int>>& grid) {
  4.         const int len1 = grid.size();
  5.         const int len2 = grid[0].size();
  6.         int dp[len1][len2];
  7.         //初始化边界数据
  8.         dp[0][0] = grid[0][0];
  9.         for(int i = 1; i < len1; i++){
  10.             dp[i][0] = grid[i][0] + dp[i - 1][0];
  11.         }
  12.         for(int i = 1; i < len2; i++){
  13.             dp[0][i] = grid[0][i] + dp[0][i - 1];
  14.         }
  15.         for(int i = 1; i < len1; i++){
  16.             for(int j = 1; j < len2; j++){
  17.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  18.             }
  19.         }
  20.         return dp[len1 - 1][len2 - 1];
  21.     }
  22. };

最大正方形

  1. 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
  3. 示例:
  5. 输入: 
  7. 1 0 1 0 0
  8. 1 0 1 1 1
  9. 1 1 1 1 1
  10. 1 0 0 1 0
  12. 输出: 4
  1. class Solution {
  2. public:
  3.     int maximalSquare(vector<vector<char>>& matrix) {
  4.         const int m = matrix.size();
  5.         if(m == 0) return 0;
  6.         const int n = matrix[0].size();
  7.         int dp[m][n], ans = 0;
  8.         for (int i = 0; i < m; i++) {
  9.             for (int j = 0; j < n; j++) {
  10.                 dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
  11.                 ans = max(ans, dp[i][j]);
  12.             }
  13.         }
  14.         for(int i = 1; i < m; i++){
  15.             for(int j = 1; j < n; j++){
  16.                 if(matrix[i][j] == '1'){
  17.                     dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
  18.                     ans = max(ans, dp[i][j]);
  19.                 }
  20.             }
  21.         }
  22.         return ans * ans;
  23.     }
  24. };

全为1的正方形

  1. 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
  5. 示例 1：
  7. 输入：matrix =
  8. [
  9.   [0,1,1,1],
  10.   [1,1,1,1],
  11.   [0,1,1,1]
  12. ]
  13. 输出：15
  14. 解释： 
  15. 边长为 1 的正方形有 10 个。
  16. 边长为 2 的正方形有 4 个。
  17. 边长为 3 的正方形有 1 个。
  18. 正方形的总数 = 10 + 4 + 1 = 15.
  1. class Solution {
  2. public:
  3.     int countSquares(vector<vector<int>>& matrix) {
  4.         int m = matrix.size();
  5.         if(m == 0) return 0;
  6.         int n = matrix[0].size();
  7.         for(int i = 1; i < m; i++){
  8.             for(int j = 1; j < n; j++){
  9.                 if(matrix[i][j] == 1){
  10.                      matrix[i][j] = min(min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]) + 1;
  11.                 }
  12.             }
  13.         }
  14.         int ans = 0;
  15.         for(int i = m - 1; i >= 0; i--){
  16.             for(int j = n - 1; j >= 0; j--){
  17.                 ans += matrix[i][j];
  18.             }
  19.         }
  20.         return ans;
  21.     }
  22. };

不同的二叉搜索树

  1. 输入: 3
  2. 输出: 5
  3. 解释:
  4. 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
  6.    1         3     3      2      1
  7.     \       /     /      / \      \
  8.      3     2     1      1   3      2
  9.     /     /       \                 \
  10.    2     1         2                 3
  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.     int G[100] = {0};
  5.     G[0] = 1; 
  6.     G[1] = 1;
  7.     G[2] = 2;
  8.     for (int i = 3; i <= n; ++i) {
  9.         for (int j = 1; j <= i; ++j) {
  10.             G[i] += G[j - 1] * G[i - j];
  11.         }
  12.     }
  13.     return G[n];
  14.     }
  15. };

最小路径和

  1. 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
  3. 说明：每次只能向下或者向右移动一步。
  5. 示例:
  7. 输入:
  8. [
  9.   [1,3,1],
  10.   [1,5,1],
  11.   [4,2,1]
  12. ]
  13. 输出: 7
  14. 解释: 因为路径 1→3→1→1→1 的总和最小。
  1. class Solution {
  2. public:
  3.     int minPathSum(vector<vector<int>>& grid) {
  4.         const int m = grid.size();
  5.         if(m == 0) return 0;
  6.         const int n = grid[0].size();
  7.         int dp[m][n];
  8.         dp[0][0] = grid[0][0];
  9.         for(int i = 1; i < n; i++) dp[0][i] = grid[0][i] + dp[0][i - 1];
  10.         for(int i = 1; i < m; i++) dp[i][0] = grid[i][0] + dp[i - 1][0];
  11.         for(int i = 1; i < m; i++){
  12.             for(int j = 1; j < n; j++){
  13.                 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  14.             }
  15.         }
  16.         return dp[m - 1][n - 1];
  17.     }
  18. };

数塔问题

  1. 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
  3. 例如，给定三角形：
  5. [
  6.      [2],
  7.     [3,4],
  8.    [6,5,7],
  9.   [4,1,8,3]
  10. ]
  11. 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
  1. class Solution {
  2. public:
  3.     int minimumTotal(vector<vector<int>>& triangle) {
  4.         const int maxn = triangle.size();
  5.         int dp[maxn][maxn];
  6.         for(int i = 0; i < maxn; i++){
  7.             dp[maxn - 1][i] = triangle[maxn - 1][i];
  8.         }
  9.         for(int i = maxn - 2; i >= 0; i--){
  10.             for(int j = 0; j <= i; j++){
  11.                 dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
  12.             }
  13.         }
  14.         return dp[0][0];
  15.     }
  16. };

股票问题

  1. 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
  2. 示例 1:
  3. 输入: [7,1,5,3,6,4]
  4. 输出: 5
  5. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  6.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         const int len = prices.size();
  5.         if(len == 0) return 0;
  6.         int dp[len][2];
  7.         dp[0][0] = 0;
  8.         dp[0][1] = -prices[0];
  9.         for(int i = 1; i < len; i++){
  10.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  11.             dp[i][1] = max(dp[i - 1][1], - prices[i]);
  12.         }
  13.         return dp[len - 1][0];
  14.     }
  15. };

最长上升子序列

这题以前写过，这里再写一遍熟悉一下题目
把动态规划题目的步骤在扩展一点：

  1. 定义数组含义
  2. 定义计算方式
  3. 给初值
  4. 考虑输出结果（这一步之前一直忽略，其实有很多题目都是输出过程中的最大值的）
  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         const int len = nums.size();
  5.         if(len == 0) return 0;
  6.         int dp[len], max_len = -1;
  7.         fill(dp, dp + len, 1);
  8.         for(int i = 0; i < len; i++){
  9.             for(int j = 0; j < i; j++){
  10.                 if(nums[i] > nums[j] && (dp[j] + 1 > dp[i])){
  11.                     dp[i] = dp[j] + 1;
  12.                 }
  13.             }
  14.             max_len = max(max_len, dp[i]);
  15.         }
  16.         return max_len;
  17.     }
  18. };

最长回文子串

题目：https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/

要点：

  1. 初始化长度为1、2的字串
  2. 最外层循环，长度从3开始

步骤：

  1. 下定义：dp[i][j]的含义是从第i个到第j个的子串是否是回文
  2. 给数组：如果头尾相等且掐头去尾的子串是回文，那么当前的也是回文
  3. 给初值：先初始化单个字符以及长度为2的字符串
  4. 输出：需要在判断的过程中就记录最大的长度
  1. class Solution {
  2. public:
  3.     string longestPalindrome(string s) {
  4.         const int len = s.size();
  5.         if(len == 0) return "";
  6.         int dp[len + 1][len + 1];
  7.         int ans = 1, ans_i = 0;
  8.         memset(dp, 0, sizeof(dp));
  9.         dp[0][0] = 1;
  11.         for(int i = 1; i < len; i++){
  12.             dp[i][i] = 1;
  13.             if(s[i - 1] == s[i]){
  14.                 dp[i - 1][i] = 1;
  15.                 ans_i = i - 1;
  16.                 ans = 2;
  17.             }
  18.         }
  20.         for(int L = 3; L <= len; L++){
  21.             for(int i = 0; i + L - 1 < len; i++){
  22.                 int j = i + L - 1;
  23.                 if(s[i] == s[j] && dp[i + 1][j - 1] == 1) {
  24.                     dp[i][j] = 1;
  25.                     ans_i = i;
  26.                     ans = max(ans, L);
  27.                 }
  28.             }
  29.         }
  31.         return s.substr(ans_i, ans);
  32.     }
  33. };

买卖股票的最佳时机含冷冻期

题目：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/submissions/

与原始版本不同的地方是，这题初值需要额外定义第一天的，另外就是持有股票的转移是从前天开始，而不是昨天

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         const int len = prices.size();
  5.         if(len <= 1) return 0;
  6.         int dp[len][2];
  7.         dp[0][0] = 0;
  8.         dp[0][1] = - prices[0];
  9.         dp[1][0] = max(dp[0][0], dp[0][1] + prices[1]);
  10.         dp[1][1] = max(dp[0][1], dp[0][0]- prices[1]);
  11.         for(int i = 2; i < len; i++){
  12.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  13.             dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
  14.         }
  15.         return dp[len - 1][0];
  16.     }
  17. };

完全平方数

题目：https://leetcode-cn.com/problems/perfect-squares/submissions/
这题算是自己独立写出来的8，还挺有成就感的

  1. class Solution {
  2. public:
  3.     int numSquares(int n) {
  4.         // 下定义：dp[i]的含义是组成i这个数的时候，所需要的最少的完全平方数
  5.         // 找关系：先找出小于i的最大的一个完全平方数a，那么有dp[i] = dp[i - a] + 1;
  6.         // 给初值：dp[0] = 0, dp[1] = 1
  7.         const int num = n;
  8.         int dp[num + 1];
  9.         dp[0] = 0, dp[1] = 1;
  10.         for(int i = 2; i <= num; i++){
  11.             int a = (int)sqrt(i);
  12.             dp[i] = 999999999;
  13.             for(int j = 1; j <= a; j++){
  14.                 dp[i] = min(dp[i], dp[i - j * j] + 1);
  15.             }
  16.         }
  17.         return dp[num];
  18.     }
  19. };

整数拆分

题目：https://leetcode-cn.com/problems/integer-break/submissions/

这题感觉有点考数学水平了，记住转移方程，下次遇到会做就行了

  1. class Solution {
  2. public:
  3.     int integerBreak(int n) {
  4.         // 下定义：dp[i]是正整数i的最大乘积
  5.         // 找关系：dp[i] = 
  6.         const int num = n;
  7.         int dp[num + 1];
  8.         fill(dp, dp + num + 1, 1);
  9.         for(int i = 3; i <= num; i++){
  10.             for(int j = 1; j < i; j++){
  11.                 dp[i] = max(dp[i], j * max(i - j, dp[i - j]));
  12.             }
  13.         }
  14.         return dp[num];
  15.     }
  16. };