算法：动态规划

• 性质：用于求解最优化问题。
  • 最优子结构：当前问题的最优解包含子问题的最优解。
  • 重叠子问题：再求取当前最优解的过程中，存在对相同子问题的重复计算。
• 70 爬楼梯
  递推式：
• 121 买卖股票的最佳时机
  递推式：
  自底向上法：
  • 时，;
  • 用两个变量分别保存和.
• 53 最大子序和
  递推式：
  自底向上法：
  • 时，;
  • 时，
  • 记录最大子序和
• 198 打家劫舍
  递推式：

int rob(int* nums, int numsSize){
    // dp: c[i]=max(c[i-2]+num[i], c[i-1])
    int maxMoney = 0;
    int pre1 = 0;
    int pre2 = 0;
    for (int i=0; i<numsSize; i++){
        if (pre1+nums[i]>=pre2){
            maxMoney = pre1+nums[i];
        }else{
            maxMoney = pre2;
        }
        pre1 = pre2;
        pre2 = maxMoney;
    }
    return maxMoney;
}

• 55 跳跃游戏
  递推式：
  自底向上法：
  • maxPosition记录当前数组能往下走的最大步(每步减1)：
    
• 62 不同路径
  动态规划，递推式：
  
  组合数学：
• 322 零钱兑换
  递推式：
• 300 最长上升子序列
  递推式：
  自底向上法：
  • 用一个数组记录当前的LIS, dp值记录其长度。
  • 迭代时，查找在LIS数组中的位置，并放入相应位置。（升序数组可用二分查找法）

int lengthOfLIS(int* nums, int numsSize){
    int dp = 0;
    int lisArr[numsSize+1];
    for (int i=0; i<numsSize; i++){
        if (i==0 || nums[i]>lisArr[dp-1]){
            lisArr[dp] = nums[i];
            dp++;
        }else{
            for (int j=0; j<dp; j++){ // 可用二分查找法，O(logn)
                if (nums[i]<=lisArr[j]){
                    lisArr[j] = nums[i];
                    break;
                }
            }
        }
    }
    return dp;
}

• 1035 不相交的线
  这是一道经典DP题目变型：最长公共子串LCS
  递推式：
  

public int maxUncrossedLines(int[] A, int[] B) {
    // Longest common subsequence
    int alen = A.length;
    int blen = B.length;
    int[][] c = new int[alen+1][blen+1];
    for (int i=1; i<alen+1; i++){
        for (int j=1; j<blen+1; j++){
            if (A[i-1]==B[j-1]) // 如果最后的两个值相等
                c[i][j]=c[i-1][j-1]+1;
            else if (c[i-1][j]>c[i][j-1]){ // 如果最后两值不等
                c[i][j] = c[i-1][j]; // 取[i-1][j]和[i][j-1]最大的一个
            }else
                c[i][j] = c[i][j-1];
        }
    }
    return c[alen][blen];
}