动态规划

动态规划

1、划分状态，划分子问题
2、状态表示，让计算机理解子问题 f[i][3]
3、状态转移，父问题如何由子问题推导出来
4、确定边界，确定初始状态，最小子问题，最终状态

• 定义数组元素的含义
• 找出数组元素间的关系式
• 找出初始条件

青蛙跳台接
int f(int n){
    if(n<=1)
        return n;
    int dp[n+1];
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

机器人走棋盘
int uniquePaths(int m,int n){
    if (m <= 0 || n <= 0) {
        return 0;
    }
    int dp[m][n];
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
      dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}