c语言动态规划dp(不定时间更新)

### 核心思想:
 
 类似于分治，讲一个大问题转化为一个小问题，由小问题的最优解得到大问题的最优解。
 分析过程从上而下，实现过程从下而上。

### 例子

 - 例子1：有二十级台阶，每次走1或2级台阶一共有多少总走法?
 > 分析：
 >
 > 在i级台阶走法为 dp[ i ]
 > 只有两种情况：
 > 1)从i - 1 走1步(dp[i - 1])
 　2）从i - 2 走2 步(dp[i - 2])
   所以dp［ｉ］ = dp［ｉ－１］＋ｄｐ［ｉ－２］ ／／状态转移方程
 ```
 
//dp:

#include<stdio.h>
int climb(int n)
{
    
    if (n <= 2)
    {
        return n;
    }
    int* dp = (int)malloc(sizeof(int) * (n + 1));
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    int ret = dp[n];
    free(dp);
    return ret;//基础方法
}

```
一个问题总能拆解成成跟小子问题，使问题一步步分治后又循环或递归去实现.

 ----
 
 - 例子2
 假如你是一个小偷，你要去偷一条街，但是每次头的时候不能够偷相邻的两家，（每家的财富有多有少），问怎么偷才能做到所得的钱数最多？

>分析：设到达i户时偷盗的钱最多为dp【i】
>1.当我们选择偷这家时，dp[i] = dp[i - 2] + nums[i]
>2.当我们不偷这家时候,dp[i] = dp[i - 1]
>所以只需要分析二者的最大值，后一步步递归既可.```

#include<stdio.h>
#include<stdlib.h>
#define max(a,b)   ((a) > (b) ? (a) : (b))
int rob(int* nums, int n)
{
    int* dp = malloc(sizeof(int) * (n + 1));
 
    dp[0] = 0;
    dp[1] = nums[0];
 
    for (int i = 2; i <= n; i++)
    {
        dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    }
    int ret = dp[n];
    free(dp);
    return ret;
}
 
int main()
{
    int a[6] = { 1 , 0 , 2, 3 , 0 };
    printf("%d", rob(a, 6));
    return 0;
}

```

  -   自我优化：```

#include<stdio.h>
#include<stdlib.h>
 
 
int rob(int* nums, int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return nums[0];
    if (n >= 2)
    {
        return max(rob(nums, n - 2) + nums[n - 1], rob(nums, n - 1));
    }
}
 
int main()
{
    int a[6] = { 1 , 0 , 2, 3 , 0 };
    printf("%d", rob(a, 6));
    return 0;
}

```

----

 - 例子3:
  >闯关 : 
  >有一个2维数组，值的大小固定，你从左上角开始出发，走到右下角，每次只能向下或向右，每次走过都会加上走过的数组的值的大小，问最优的次数是多少？
  
  分析：
  假设当前走到第i行的第j列，只有两种情况：
  1)从a[ i ] 和[j - 1]来的
     dp【i】【j】 = dp【i 】【j - 1】 + arr【i】【j】；
  2）从a【i - 1】【j】来的。
     dp【i】【j】 = dp【i  - 1】【j】 + arr【i】【j】；

我们要取其最小值:min```

#include<stdio.h>
#include<stdlib.h>
#define Rows 3
#define COls 3//以后开二维数组时使用这种方式
 
int path(int gird[Rows][COls])
{
    int i, j;
    int dp[Rows][COls] = { 0 };
    
    for (i = 0; i < Rows; i++)
    {
        for (j = 0; j < COls;j++)
        {
            if (i == 0 && j == 0)
            {
                dp[i][j] = gird[0][0];
            }
            else if (i == 0)
            {
                dp[i][j] = dp[i][j - 1] + gird[i][j];
            }
            else if (j == 0)
            {
                dp[i][j] = dp[i - 1][j] + gird[i][j];
            }
            else
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + gird[i][j];
            }
        }
    }
    return dp[Rows - 1][COls - 1];
}
 
int main()
{
    int arr[3][3] = { 1,2,3,1,2,5,4,2,1 };
    printf("%d", path(arr));
    return 0;
}

```
  好了接下来自己去刷题吧！

(我是新手，请读者多多指正）.