再谈动态规划框架

动态规划框架

动态规划问题一般是求最值，比如求最长子序列，最小编辑距离等。

动态规划三要素：

1.存在重叠”子问题“， 如果暴力穷举，效率会非常低下，因此需要具备备忘录，DPtabel来优化穷举过程；

2. 具备最优子结构，才能通过子问题的最值得到原问题的最值。

3. 正确的”状态转移方程“，穷举所以可行解并不是一件容易的事情，这一步最为重要。

   如何列举出状态转移方程，可以遵守以下步骤：

   1. 这个问题的base case (最简单的情况) 是什么？
   2. 这个问题有什么状态？
   3. 对于每个”状态“，可以做什么”选择“ 使得”状态“发生改变？
   4. 如何定义 dp 数组/函数 的含义来表现”状态“和“选择”？

#初始化base case
dp[0][0][...]=base case
for 状态1 in 状态1的所有数值:
	for 状态2 in 状态2的所有数值:
		for ...:
			dp[状态1][状态2][...]=求最值(选择1,选择2,...)
      
# 在每个列举出来的状态中通过求最值的方法得到当前状态的最大/最小选择。for循环列举出所有的状态。状态转移体现在f(z)=min(f(x),f(y))中，z=x+y z和x，y有关系，这样可以得到最后的min值

斐波那契数列: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模1e9+7(1000000007), 如计算初始结果为:1000000008, 请返回1。

class Solution {
public:
    int fib(int n) {
			if (n==0) return 0;
      if (n==1) return 1;
      vector<int> dp;
      dp[1]=1;
      dp[2]=1;
			for (int i=3;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2])%10000007;
      }
      return dp[n-1];
    }
};

class Solution {
public:
    int fib(int n) {
			if (n==0) return 0;
      if (n==1) return 1;
      int prev=1;
      int curr=1;
			for (int i=3;i<=n;i++){
					int sums= prev+curr;
        	prev=curr;
        	curr=sums;
      }
      return sums;
    }
};

零钱交换: https://leetcode-cn.com/problems/coin-change/

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
      //如果条件满足，则返回-1，否则返回dp[amount]
    }
};